[Leetcode] 3월 3주차 문제풀이

 

드디어 밀린 릿코드 문제풀이를 오늘로 마무리한다.

 

• 680. Valid Palindrome II [Easy]

https://leetcode.com/problems/valid-palindrome-ii/

Valid Palindrome II - LeetCode

 

string s 가 주어졌을 때, 최대로(at most) 딱 한 개의 문자만 지워서 회문을 만들 수 있는지 리턴해주는 문제.

 

아래처럼 풀면 TLE가 발생한다. ㅎㅎ 

 

if(s[left] != s[right]) {	// 틀린 부분이 나타남
  if(count==0) {		// 위치를 기억해두고 왼쪽 먼저 이동
    rem_l = left;
    rem_r = right;
    left++;
  }
  else if(count==1) {	// 또 틀리면 기억한 위치로 돌아와 오른쪽 이동
    left = rem_l;
    right = rem_r;
    right--;
  }
  else
    return false;
  count++;
}

 

 

접근 방법은 같은데 왼쪽으로 이동한 경우 / 오른쪽으로 이동한 경우를 두고

while문으로 한번에 확인 후 idx를 비교해서 결과를 return 해주면 pass 한다.

 

class Solution {
public:
    bool validPalindrome(string s) {
        int left=0,right=s.size()-1;
        int count=0;
        
        int rem_l=0, rem_r=0;
        while(left < right) {
            if(s[left] != s[right]) {
                int l1=left+1, r1=right, l2=left, r2=right-1;
                while(l1<r1 && s[l1]==s[r1]) {
                    l1++; r1--;
                }
                while(l2<r2 && s[l2]==s[r2]) {
                    l2++; r2--;
                }
                
                return l1>=r1 || l2>=r2;
            }
            left++; right--;
        }
        
        return true;
    }
};

 

 

• 31. Next Permutation [Medium]

https://leetcode.com/problems/next-permutation/

Next Permutation - LeetCode

 

문제 이름에서도 알 수 있듯이 숫자가 주어지면 해당 배열의 다음 순열을 리턴해주면 되는 문제이다.

 

풀다가 짜증 나서 그냥 next_permutation 라이브러리를 가져다썼는데... 문제의 의도는 그게 아니겠지..

 

discuss에서 풀이를 보고 이해했다.

 

class Solution {
public:
    
    void nextPermutation(vector<int>& nums) {
        int first_d = nums.size()-2;
        while(first_d >= 0 && nums[first_d] >= nums[first_d+1]) first_d--;
        
        if(first_d < 0) {
            reverse(nums.begin(), nums.end());
            return;
        }
        
        int swap_d = nums.size()-1;
        while(nums[swap_d] <= nums[first_d]) swap_d--;
        
        swap(nums[swap_d], nums[first_d]);
        reverse(nums.begin() + first_d + 1, nums.end());
    }
};

 

- first_d : nums[first_d] < nums[first_d+1] 을 만족하는 가장 큰 Idx

- swap_d : (first_d < swap_d)를 만족하면서 nums[first_d] < nums[swap_d]를 만족하는 가장 큰 idx

 

만약 first_d가 존재하지 않는다면 가장 마지막 순열이므로 

다시 처음으로 돌아간 nums를 리턴해주면 된다. (reverse(nums.begin(), nums.end())

 

first_d, swap_d가 모두 찾아졌으면 두 수를 swap해주고 

마지막으로 nums[first_d+1:] first_d 인덱스 이후의 순서를 reverse 해준다.

 

ex) 5, 3, 4, 2 

 

- first_d의 경우 위 조건을 만족하는 idx값 1을 가짐

- swap_d의 경우 위 조건을 만족하는 Idx값 2를 가짐

 

first_d와 swap_d를 바꿔주면 -> 5, 4, 3, 2

first_d 인덱스 이후의 순서를 reverse 하게 되면 -> 5, 4, 2, 3 (정답)

 

 

• 84. Largest Rectangle in Histogram [hard]

https://leetcode.com/problems/largest-rectangle-in-histogram/

Largest Rectangle in Histogram - LeetCode

 

원래 아래 나오는 maximal rectangle문제를 풀려고 하다가 너무 어려워서 discuss를 들어갔는데

이 84번 문제를 기반으로 풀었다는 사람이 꽤 있어서 이 문제를 먼저 잡았다.

 

근데 역시나 어려워서 못 풀었다 ㅎㅎㅎㅎ....

 

discuss를 보니 이 문제는 대부분 stack을 이용해 푼 것 같다.

 

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        
        stack<int> s;
        heights.push_back(0);	// s에는 heights의 Idx값이 들어감
        
        int sizemax=0;
        for(int idx=0;idx<heights.size();idx++) {	// heights를 한번 순회
            
            while(s.size() && heights[s.top()] >= heights[idx]) {
                int h = heights[s.top()];
                s.pop();
                
                int index = s.size() ? s.top() : -1;
                
                int tmp_size = (idx-index-1)*h;
                sizemax = max(sizemax, tmp_size);
            }
            s.push(idx);	// heights[s.top()] < heights[idx] 일 경우 계속 push
        }
        
        return sizemax;
    }
};

 

for문 안에를 보면, 만약 stack의 가장 위에 있는 값이 현재 idx 값보다 작으면 계속 stack에 push 한다.

 

다시 말해 stack에는 (1, 5, 6) 이런 식으로 top으로 갈수록 큰 값이 놓일 수밖에 없다.

만약 현재 idx가 6보다 작은 값이 온다면 하나씩 빼주면서 넓이를 계산해준다.

 

input은 2, 1, 5, 6, 2, 3으로 들어오고

stack이 (1, 2, 3) ( 각 Index에 해당하는 값은 (1, 5, 6) )으로 쌓였을 때 그다음 값 idx = 4, heights[idx]=2가 오면

h=6, index는 2, idx는 4가 된다. 

 

넓이를 구해주면 6 * (4-2-1) = 6이 된다.

 

그다음으로 stack (1, 2)가 남아있는데 heights[2] = 5로 아직 while문의 조건을 만족한다.

이때 idx는 변함이 없고 index만 1로 변경된다.

 

그래서 여기서 구해진 넓이는 5 * (4-1-1) = 10이 된다.

 

뭔가 굉장히 똑똑한 방법이다.... 🧐

 

 

 

• 85. Maximal Rectangle [hard]

https://leetcode.com/problems/maximal-rectangle/

Maximal Rectangle - LeetCode

 

이 문제를 풀려고 위에 문제를 풀고 왔는데 도저히 응용이 안됐다.

이건 discuss를 봐도 한참 이해가 안 가서 이해하는데만 이틀이 걸린 것 같다.

 

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        
        if(matrix.size() == 0)
            return 0;
        
        int n = matrix.size();
        int m = matrix[0].size();
        
        vector<int> left(m), height(m);
        vector<int> right(m, m);
        
        int result=0;
        for(int i=0;i<n;i++) {
            int cur_left=0, cur_right=m;
            for(int j=0;j<m;j++) {
                if(matrix[i][j] == '1') height[j]++;
                else height[j]=0;
            }
            
            for(int j=0;j<m;j++) {
                if(matrix[i][j] == '1') {
                    left[j] = max(cur_left,left[j]);
                }
                else {
                    left[j] = 0;
                    cur_left = j+1;
                }
            }
            
            for(int j=m-1;j>=0;j--) {
                if(matrix[i][j] == '1') {
                    right[j] = min(cur_right,right[j]);
                }
                else {
                    cur_right = j;
                    right[j] = m;
                }
            }
            
            for(int j=0;j<m;j++) {
                result = max(result, (right[j]-left[j])*height[j]);
            }
        }
        
        return result;
    }
};

 

한 행씩 계산해 나가면서 최대 넓이를 구하는데, 이전 행에서 구해진 값이 현재 행에 영향을 주기 때문에 dp라고 할 수 있다.

 

아래 discuss 링크 설명을 천천히 읽어보면서 그려보면 이해가 좀 더 쉽게 간다..

 

https://leetcode.com/problems/maximal-rectangle/discuss/29054/Share-my-DP-solution

Share my DP solution - LeetCode Discuss

 

 

 

• 209. Minimum Size Subarray Sum [Medium]

 

https://leetcode.com/problems/minimum-size-subarray-sum/

Minimum Size Subarray Sum - LeetCode

 

target과 배열이 주어지면 연속적인 숫자의 합이 target과 같거나 큰 경우를 만족하면서

연속적인 숫자들의 개수가 가장 작은 수를 리턴해주는 문제이다.

 

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        
        int start=0, end=0, min_num = nums.size()+1;
        int sum = nums[end];
        
        while(start<=end && end < nums.size()) {
            
            if(sum >= target) {
               // cout << start << " " << end << endl;
                int numofsum = (end - start) + 1;
                min_num = (min_num > numofsum) ? numofsum : min_num;
                
                sum -= nums[start++];
            }
            else {
                if(end != nums.size()-1)
                    sum += nums[++end];
                else
                    end++;
            }
        }
        
        if(min_num == (nums.size()+1))
            return 0;
        else
            return min_num;
    }
};

 

요 문제는 그냥 간단하게 start와 end 인덱스를 변경해가면서 가장 작은 min_num을 리턴해주는 방식으로 구현했다.

 

 

• 567. Permutation in String [Medium]

https://leetcode.com/problems/permutation-in-string/

Permutation in String - LeetCode

 

s1, s2의 문자열이 주어지고 s1의 순열을 s2가 포함하고 있다면 true를 리턴해주는 문제.

 

이 문제는 딱히 순열을 고려할 필요가 없다.

s2가 어떤 순열이든 포함만 하면 되기 때문에 s1의 모든 문자열을 연속적으로 가지고 있는지만 체크해주면 된다.

 

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        multiset<char> ms(s1.begin(), s1.end());
        
        for(int idx2=0;idx2<s2.size();idx2++) {
            if(ms.count(s2[idx2])) {
                ms.erase(ms.find(s2[idx2++]));
                
                int cnt = s1.size()-1;
                while(cnt > 0 && idx2<s2.size()) {
                    if(ms.count(s2[idx2])) {
                        ms.erase(ms.find(s2[idx2++]));
                    }
                    else {
                        return false;
                    }
                    cnt--;
                }
            }
        }
        
        if(ms.size())
            return false;
        else
            return true;
    }
};

 

multiset을 이용해서 s1을 담아뒀다가 하나씩 제거해가며 확인하면 풀 수 있다.

 

 

• 480. Sliding Window Median [hard]

https://leetcode.com/problems/sliding-window-median/

Sliding Window Median - LeetCode

k개의 숫자를 담는 sliding window를 움직이면서 

짝수일 경우 가운데 두 수의 평균값, 홀수일 경우 가장 가운데 값을 vector로 쌓아 리턴해주면 되는 문제이다.

 

여기서 가운데 값은 k개의 숫자가 정렬되어 있을 때 값을 말한다.

 

문제 그대로 index값들을 움직여주면서 sort 한 이후에 가운데 혹은 평균값을 리턴해줬는데 TLE가 발생한다.

 

보통 두 개의 priority queue를 사용해서 문제를 푼 사람들이 많았고, 아래는 multiset을 이용한 풀이다.

 

 

class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        multiset<int> window(nums.begin(), nums.begin() + k);
        auto mid = next(window.begin(), k / 2);
        vector<double> medians;
        for (int i=k; ; i++) {

            // Push the current median.
            medians.push_back((double(*mid) + *prev(mid, 1 - k%2)) / 2);

            // If all done, return.
            if (i == nums.size())
                return medians;

            // Insert nums[i].
            window.insert(nums[i]);
            if (nums[i] < *mid)
                mid--;

            // Erase nums[i-k].
            if (nums[i-k] <= *mid)
                mid++;
            window.erase(window.lower_bound(nums[i-k]));
        }
    }
};

 

다음에 Priority queue로 다시 풀어봐야겠다.