[Leetcode] 2월 2주차 문제풀이 (array, string)

 

array와 string을 위주로 문제를 풀어봤던 2주차...

정리를 뒤늦게 하고있다.. 하하 ☺️

 

 

• 1047. Remove All Adjacent Duplicates In String [Easy]

 

https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/

Remove All Adjacent Duplicates In String - LeetCode

 

주어진 string에서 인접해있는 중복 문자들을 제거하는 문제

 

단순하게 stack을 이용해서 현재 넣으려는 문자와 stack의 가장 위에 있는 값이 같으면 제거하고,

다르면 stack에 넣어주는 방식으로 구현했다.

 

class Solution {
public:
    string removeDuplicates(string S) {
        string result = "";
        
        for(int idx=0;idx<S.size();idx++) {
            if(result.length() == 0) {
                result += S[idx];
                continue;
            }
            
            char cur = result[result.length()-1];
            
            if(cur == S[idx]) {
                result.erase(result.length()-1, 1);
            } else {
                result += S[idx];
            }
        }
        
        return result;
    }
};

 

 

• 921. Minimum Add to Make Parentheses Valid [Medium]

 

https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/

Minimum Add to Make Parentheses Valid - LeetCode

 

주어진 소괄호가 완전하게 짝을 이루기 위해서는 최소 몇 개의 소괄호가 필요한지 리턴해주는 문제

 

이것도 위 문제랑 동일하게 stack을 이용해서 풀었다.

마지막엔 stack의 사이즈만 리턴해주면 된다.

 

class Solution {
public:
    int minAddToMakeValid(string S) {
        string result = "";
        int r_length = result.size();
        
        for(char& c : S){
            if(result.size() && (result.back()=='(' && c==')')) {
                result.pop_back();
            }
            else {
                result.push_back(c);
            }
        }
        
        return result.size();
    }
};

 

 

• 1703. Minimum Adjacent Swaps for K Consecutive Ones [hard]

 

https://leetcode.com/problems/minimum-adjacent-swaps-for-k-consecutive-ones/

Minimum Adjacent Swaps for K Consecutive Ones - LeetCode

 

와 이 문제는 너무 어렵다.. 어려워서 이틀 고민하다가 못 풀고 discuss를 봤는데..

그래도 그냥 모르겠어서 안 풀고 넘어갔다.

나중에 돌아와서 풀어볼 문제...

 

 

 

• 15. 3Sum [medium]

 

https://leetcode.com/problems/3sum/

3Sum - LeetCode

 

주어진 array에서 'a+b+c=0' 세 숫자의 합이 0이 되는 조합들을 모두 찾아서 리턴하는 문제

 

이건 도저히 생각 안 나서 discuss를 참고하고 풀었던 것 같다.

설마 start, end를 잡고 왔다 갔다 하면서 더할 줄이야...

 

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        
        sort(nums.begin(), nums.end());
        
        vector<int> temp;
        for(int i=0;i<nums.size();) {
            int start = i+1;
            int end = nums.size()-1;
            
            while(start < end) {
                if(nums[i]+nums[start]+nums[end]==0){
                    result.push_back({nums[i], nums[start], nums[end]});
                    start++;
                    end--;

                    while(start<end && nums[start] == nums[start-1]) start++;
                    while(start<end && nums[end] == nums[end+1]) end--;
                }
                else if (nums[i]+nums[start]+nums[end]<0){
                    start++;
                    while(start<end && nums[start] == nums[start-1]) start++;
                }
                else {
                    end--;
                    while(start<end && nums[end] == nums[end+1]) end--;
                }
            }
            
            i++;
            
            while(i<nums.size() && nums[i] == nums[i-1])
                i++;
        }
        
        return result;
    }
};

 

 

• 16. 3Sum Closest [Medium]

 

https://leetcode.com/problems/3sum-closest/

3Sum Closest - LeetCode

 

 

 

주어진 array에서 3개의 숫자를 뽑는 건 위 문제와 유사하지만

세 숫자를 더해서 주어진 target과 가장 가까운 합을 리턴하는 문제

 

알고리즘을 머릿속으로 좀 정리하고 풀어봤어야 했는데,

그냥 막 풀다 보니 꼬여서 엄청난 submit과 wrong answer를 받다가 푼 문제...ㅎㅎ 

이 문제도 나중에 다시 풀어볼 예정이다.

 

위 문제의 풀이와 비슷하고 start, end를 움직이는 방식만 조금 바꿔주면 된다.

 

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int result=nums[0]+nums[1]+nums[2];
        
        sort(nums.begin(), nums.end());
        
        for(int idx=0;idx<nums.size();idx++) {
            int start=idx+1;
            int end = nums.size()-1;
            
            while(start<end) {
                int cur_result = nums[idx]+nums[start]+nums[end];
                if(cur_result == target)
                    return cur_result;
                
                if(abs(target-result) > abs(target-cur_result)) {
                    result = cur_result;
                }
                
                if(cur_result > target)
                    end--;
                else
                    start++;
            }
        }
        
        return result;
    }
};

 

 

아무래도 푼 문제를 다시 정리하니까 리마인드 하는 것 같아서 도움이 된다.....

실력 좀 늘어라 😑...