[Leetcode] 3월 1-2주차 문제 풀이

 

3월에는 문제를 2월만큼 많이 못 풀었다. 

4월엔 많이 풀어야지.... 😴

 

Array / String

 

• 415. Add Strings [Easy]

https://leetcode.com/problems/add-strings/

Add Strings - LeetCode

 

string으로 표현된 양의 정수가 두 개 주어지면 더한 값을 string으로 다시 리턴해주는 문제.

 

그냥 간단하게 string을 reverse하고 각 자릿수를 int로 변경해서 더해준 후 string에 push했다.

 

class Solution {
public:
    string addStrings(string num1, string num2) {
        
        int length = (num1.size() > num2.size()) ? num1.size() : num2.size();
        
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        
        int remaind = 0, idx1=0, idx2=0;
        string result="";
        while(idx1<num1.size() || idx2<num2.size() || remaind) {
            int left = (idx1<num1.size()) ? num1[idx1++]-'0' : 0;
            int right = (idx2<num2.size()) ? num2[idx2++]-'0' : 0;
            
            left = left+right+remaind;
            remaind = left/10;
            result.push_back(left%10+'0');
        }
        
        reverse(result.begin(), result.end());
            
        return result;
    }
};

 

굳이 num1, num2를 reverse할 필요 없이 계산 후 결과를 reverse 해주면 됐을 텐데.....

 

 

• 695. Max Area of Island [Medium]

https://leetcode.com/problems/max-area-of-island/

Max Area of Island - LeetCode

 

2d array가 주어지고 0은 water, 1은 land로 표현된다.

land는 상하좌우 4방향으로만 연결되어있고 주어진 array에서 가장 면적이 큰 land의 수를 리턴하는 문제다.

 

이것도 보자마자 bfs가 떠오르는 문제다.

 

그래서 queue를 사용해 아래처럼 좌표값을 넣어서 문제를 풀었다.

 

queue<pair<int,int>> q;

 

상하좌우로 움직여야 할 때에는 아래처럼 4x2 vector를 만들어서 사용했다.

 

vector<vector<int>> direction {{1,0}, {-1,0}, {0,1}, {0,-1}};

 

그리고 방문한 land에 대해서는 checked[][]와 같은 배열을 만들기보다는 그냥 0으로 변경해줬다.

 

그런데 위에 방법처럼 queue를 이용했더니 runtime이 절반에도 못 미쳐서 그냥 recursive로 구현했더니 더 빠르다..

왜지... 🧐

class Solution {
public:
    int dfs(vector<vector<int>>& grid, int i, int j) {
        if(i<0 || j<0 || i >= grid.size() || j >= grid[0].size() || !grid[i][j])
            return 0;
        
        grid[i][j] = 0;
        return dfs(grid, i-1, j) + dfs(grid, i+1, j) + dfs(grid, i, j-1) + dfs(grid, i, j+1) + 1;
    }
    
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int max_result=0;
        
        for(int i=0;i<grid.size();i++) {
            for(int j=0;j<grid[0].size();j++) {
                if(grid[i][j] == 1) {
                    max_result = max(max_result, dfs(grid, i,j));
                }
            }
        }
        
        return max_result;
    }
};

 

 

• 56. Merge Intervals [Medium]

https://leetcode.com/problems/merge-intervals/

Merge Intervals - LeetCode

 

intervals[i] = [start_i, end_i] 로 구성된 intervals vector들이 주어지면 

겹치는 구간들을 모두 합쳐서 겹치지 않는 intervals의 vector를 리턴해주는 문제이다.

 

예를 들어 [[1,3], [2,6], [8,10]]이 주어지면 [[1,6],[8,10]]을 리턴해야 한다.

 

일단 Intervals는 정렬된 상태로 들어오지 않기 때문에 정렬이 필요하다.

 

 

나는 start, end를 각각 vector로 만들어서 아래처럼 넣어주고 정렬했다.

 

vector<int> s,e;
        
for(auto interv : intervals) {
  s.push_back(interv[0]);
  e.push_back(interv[1]);
}

sort(s.begin(), s.end());
sort(e.begin(), e.end());

 

위에 간단히 예를 든 것으로 설명하자면 

s = [1, 2, 8] / e = [3, 6, 10]이 들어있게 만들어줬다.

 

그리고 현재 구간에 대해 start/end를 각각 res_s = s[0], res_e=e[0]으로 초기화한 후 

다음으로 들어오는 start 값이 end보다 작다면 단순히 res_e를 e[1]로 변경,

end보다 크다면 res_s와 res_e를 vector에 넣고 res_s=s[1], res_e=e[1]로 변경해준다.

 

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;
        
        vector<int> s,e;
        
        for(auto interv : intervals) {
            s.push_back(interv[0]);
            e.push_back(interv[1]);
        }
        
        sort(s.begin(), s.end());
        sort(e.begin(), e.end());
        
        int res_s=s[0], res_e=e[0];
        for(int idx=1;idx<s.size();idx++) {
            if(s[idx] <= res_e) {
                res_e = e[idx];
            }
            else {
                result.push_back({res_s, res_e});
                
                res_s = s[idx];
                res_e = e[idx];
            }
        }
        
        result.push_back({res_s, res_e});
        
        return result;
    }
};

 

그런데 이렇게 하면 공간도 많이 쓰고 시간도 비효율적이다.

 

c++에서는 sort함수의 마지막 매개변수를 이용해 원하는 sort함수를 만들 수 있다.

 

아래 코드는 위 코드와 방법은 동일한데 시간/공간적으로 더 효율적인 코드다..

 

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;
        
        sort(intervals.begin(), intervals.end(), 
             [](const vector<int> &a, const vector<int> &b) {return a[0] < b[0];});
        
        result.push_back(intervals[0]);
        
        for(int idx=1;idx<intervals.size();idx++) {
            auto& res_e = result.back();
            if(intervals[idx][0] <= res_e[1]) {
                res_e[1] = (res_e[1] <= intervals[idx][1]) ? intervals[idx][1] : res_e[1];
            }
            else {
                result.push_back(intervals[idx]);
            }
        }
        
        return result;
    }
};

 

 

 

Algorithm study

 

알고리즘 스터디에서 내준 문제도 추가적으로 풀어봤다.

2주 동안 6문제를 푸는 게 왜 이렇게 힘든지 ㅠ.ㅜ

 

 

• 873. Length of Longest Fibonacci Subsequence [Medium]

https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/

Length of Longest Fibonacci Subsequence - LeetCode

 

값이 증가하는 양의 정수들을 가진 arr가 주어진다.

이 arr에서 피보나치 수열을 표현한다면 가장 길게 표현되는 길이는 얼마인지 리턴해주면 된다.

 

처음에는 recursive로 어떻게 해결해보려 했으나 실패했다..

idx도 연속적이어야 한다고 생각했는데 수가 띄엄띄엄 존재해도 a_i + a_j = a_k 만 만족한다면 가능하다.

 

그래서 아래 discuss에 소개된 코드로 풀어봤다.

머리가 좋네...ㅎㅎ

 

unordered_set의 활용이 기가 막히다.

class Solution {
public:
    
    int lenLongestFibSubseq(vector<int>& arr) {
        
        unordered_set<int> s(arr.begin(), arr.end());
        int result=0;
        
        for(int i=0;i<arr.size()-1;i++) {
            for(int j=i+1;j<arr.size();j++) {
                int a=arr[i], b=arr[j], l=2;
                
                while(s.count(a+b)) {
                    b=a+b; a=b-a; l++;
                }
                
                result = max(result, l);
            }
        }
        
        return (result>2)?result:0;
    }
};

 

 

• 44. Wildcard Matching [hard]

https://leetcode.com/problems/wildcard-matching/

Wildcard Matching - LeetCode

 

string s와 pattern p가 주어지고 p에는 알파벳 이외에 *나 ?의 문자가 들어갈 수 있다.

*는 어떤 sequence의 단어와도 매칭이 가능하고, ?는 딱 하나의 문자에 매칭이 가능한 특성을 가지고 있다.

 

이때 s내에서 p의 패턴을 가질 수 있는지 true/false를 리턴해주는 문제이다.

 

이건 index를 요래조래 바꿔서 해보려고 했는데 쉽지가 않았다 ㅠㅠ

 

문제 자체는 dfs+backtracking..?으로 discuss에서 보고 풀어봤는데, dp로 풀 수 있는 문제다.

다음에 dp로 꼭 풀어볼 문제..

 

class Solution {
public:
    bool isMatch(string s, string p) {
        int i=0, j=0, srem = -1, prem=-1;
        
        while(i < s.size()) {
            if(j < p.size() && ((s[i]==p[j]) || p[j] == '?')) {
                i++; j++;
            }
            else if (j < p.size() && p[j] == '*') {
                prem = j;
                srem = i;
                j++;
            }
            else if (prem != -1) {
                j = prem+1;
                srem++;
                i = srem;
            }
            else
                return false;
        }
        
        while(p[j]=='*' && j<p.size()) j++;
        
        return (j==p.size());
    }
};