[Leetcode] 2월 4주차 문제 풀이

 

4주차에는 온라인 코테가 있어서 대비를 하느라 문제를 엄청 많이 풀었었다...

자신없었던 dfs관련 문제도 풀어보고 시험 기출문제도 찾아서 풀었다. (부질없었음)

 

 

---

 

Tree / Graph

dfs하면 tree, graph 문제..

easy/medium/hard 문제로 각각 풀어봤는데 아래 세 문제를 풀고나면 dfs는 정복한 느낌이 든다. (ㅎㅎ)

 

• 111. Minimum Depth of Binary Tree [Easy]

 

leetcode.com/problems/minimum-depth-of-binary-tree/

Minimum Depth of Binary Tree - LeetCode

 

루트노드가 주워지면 가장 최소 depth를 구하는 문제.

 

queue를 이용해서 왼쪽 자식과 오른쪽 자식 둘 다 없는 경우 count하던 depth를 리턴해주면 된다.

 

class Solution {
public:
    int minDepth(TreeNode* root) {        
        if(!root)
            return 0;
        
        queue<TreeNode*> q;
        
        q.push(root);
        
        int result=0;
        while(!q.empty()) {
            TreeNode* cur = q.front();
            int size = q.size();
            result++;
            
            for(int i=0;i<size;i++) {
                cur = q.front();
                q.pop();
                
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
                
                if(!cur->left && !cur->right)
                    return result;
            }
        }
        
        return 0;
    }
};

 

 

• 994. Rotting Oranges [Medium]

https://leetcode.com/problems/rotting-oranges/

Rotting Oranges - LeetCode

 

mxn grid가 주어지고 0은 empty cell, 1은 fresh orange, 2는 rotten orange를 의미한다.

매 분마다 rotten orange의 상하좌우에 위치한 fresh orange는 썩은 오렌지가 된다.

모든 fresh orange가 rotten orange가 되는 최소 분을 리턴해주는 문제다.

 

요것도 문제만 딱 읽으면 bfs로 푸는 문제라는게 느껴진다...

 

queue에 pair(i,j)를 넣어서 bfs로 풀면 된다.

 

class Solution {
public:
    vector<vector<int>> direction {{0,1}, {0,-1}, {1,0}, {-1,0}};
    
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        queue<pair<int, int>> rot;
        
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(grid[i][j] == 2) 
                    rot.push(make_pair(i,j));
            }
        }
        
        int minute = 0;
        while(!rot.empty()) {
            int size = rot.size();
            minute++;
            
            for(int k=0;k<size;k++) {
                int cur_m = rot.front().first;
                int cur_n = rot.front().second;
                rot.pop();
                
                grid[cur_m][cur_n] = 2;
                
                for(int d=0;d<4;d++){
                    int move_m = cur_m + direction[d][0];
                    int move_n = cur_n + direction[d][1];
                    
                    if(move_m < 0 || move_n < 0 || move_m >= m || move_n >= n) {
                        continue;
                    }
                    
                    if(grid[move_m][move_n] == 1) {
                        rot.push(make_pair(move_m, move_n));
                        grid[move_m][move_n] = 2;
                    }
                }
            }
            
            if(rot.empty())
                minute--;
        }
        
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++) {
                if(grid[i][j] == 1)
                    return -1;
            }
        }
        
        return minute;
    }
};

 

위에 방법으로 풀면 마지막에 모든 grid를 다시 돌면서

1이 존재하는 경우 -1을 리턴해주기 때문에 시간이 좀 더 걸린다.

 

1인 경우 count를 해줬다가 count해준 개수와 썩어버린 오렌지 개수가 맞지 않으면 -1을 리턴해주면 시간이 빨라진다.

 

 

• 815. Bus Routes [hard]

https://leetcode.com/problems/bus-routes/

Bus Routes - LeetCode

 

매개변수로 vector<vector<int>> routes, int source, int target이 들어온다.

여기서 routes는 만약 route[0] = {0, 3, 5} 라면 0번째 버스가 정류장 0->3->5->0->3->5...

이렇게 계속 반복한다는 것을 의미한다.

 

source에서 target으로 이동할 때 가장 최소로 타야하는 버스의 수를 리턴하는 문제다.

 

이 문제는 어느정도 자료구조도 이용해야 했어서 풀다가 discuss를 참고했다.. 

 

 

먼저 루트 자체는 unordered map에 저장한다 (버스의 번호는 unique해서 map이 가능)

bfs로 가능한 루트를 찾기 위해 queue를 생성한다.

이 때 탑승했던 버스를 체크하기 위해 unordered set을 사용해준다.

 

지나간 루트의 경우에는 clear를 이용해 vector를 제거한다.

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        unordered_map<int, vector<int>> um;
        
        for(int i=0;i<routes.size();i++) {
            for(int j : routes[i]) {
                um[j].push_back(i);
            }
        }
        
        queue<pair<int, int>> q;
        q.push(make_pair(source, 0));
        
        unordered_set<int> checked;
        checked.insert(source);
        
        while(!q.empty()) {
            int cur_stop = q.front().first;
            int bus_num = q.front().second;
            q.pop();
            
            if(cur_stop == target)
                return bus_num;
            
            for(auto i : um[cur_stop]) {
                for(auto j : routes[i]) {
                    if(!checked.count(j)) {
                        q.push(make_pair(j, bus_num+1));
                        checked.insert(j);
                    }
                }
                routes[i].clear();
            }
        }
        
        return -1;
    }
};

 

 

Array / String

 

• 28. Implement strStr() [Easy]

https://leetcode.com/problems/implement-strstr/

Implement strStr() - LeetCode

 

이 문제는 easy라서 시도했던 문젠데 어려웠다...

푸는 내내 '아니 strstr() 함수가 있는데 굳이 이걸 왜 구현해야해..' 하면서 풀었던 기억이..

 

실제 strstr() 함수처럼 string 내에서 특정 패턴을 가진 string의 첫 idx를 리턴해주는 문제이다.

 

이 문제는 kmp알고리즘을 적용한다면 좀 더 빠른 수행시간으로 풀 수 있다.

(나중에 kmp알고리즘으로 다시 풀어봐야할 문제)

 

그냥 brute force로 풀어버렸다.

class Solution {
public:
    int strStr(string haystack, string needle) {
        
        if(!needle.length()) 
            return 0;
        
        
        for(int idx=0;idx<haystack.length();idx++) {
            
            if(needle[0] == haystack[idx]) {
                int tmp_idx = idx;
                while(++tmp_idx < haystack.length() &&
                     (tmp_idx - idx) < needle.length()) {
                    if(needle[tmp_idx-idx] != haystack[tmp_idx])
                        break;
                }
                if(tmp_idx-idx == needle.length())
                    return idx;
            }
        }
        
        return -1;
    }
};

 

 

• 48. Rotate Image [Medium]

 

https://leetcode.com/problems/rotate-image/

Rotate Image - LeetCode

 

nxn의 2dimension matrix가 주어지면 시계방향으로 90도 회전됐을 때의 matrix를 리턴하는 문제.

대신 따로 별도의 matrix를 사용하면 안되고 주어진 vector<vector<int>>의 값을 변경해줘야 한다.

 

정말 짜증나는 문제....^^!

 

3x3 index를 종이에 하나하나 적어놓고 돌렸을때랑 비교해가면서 알고리즘을 만들었는데

잘안됐다 ㅎㅎㅎㅎㅎㅎㅎㅎㅎ

 

그래서 discuss로 올라온 알고리즘 중에 가장 유사한 알고리즘을 따라서 다시 그려가면서 구현...

제발 이런 문제는... 내지마....

 

코드는 비교적 간단한데 아무튼 생각해내기까지가 굉장히 어렵다.

이건 설명하기도 어렵다...

다들 그려가면서 해보면... 이해가 간다...

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int size = matrix.size();
        
        int i=0,j=size-1;
        
        while(i<j) {
            for(int idx=0;idx<j-i;idx++) {
                swap(matrix[i][i+idx], matrix[i+idx][j]);
                swap(matrix[i][i+idx], matrix[j][j-idx]);
                swap(matrix[i][i+idx], matrix[j-idx][i]);
            }
            i++;
            j--;
        }
    }
};

 

 

 

Online Assessment

 

아마존 캐나다 온라인 테스트를 위해서 여러가지 문제를 풀어봤었다.

대부분 easy~medium 정도의 문제들이 많이 기출되는 것으로 보인다.

 

아래 4개 정도의 문제를 풀고 시험을 봤는데 물론 아래처럼 나오진 않았다.

 

다양한 범위의 알고리즘에서 출제되는 것 같고, dfs/greedy/array 위주로 많이 나오는 것처럼 보인다.

난 왜 dp가 나온거지....

 

 

• 1710. Maximum Units on a Truck [Easy]

https://leetcode.com/problems/maximum-units-on-a-truck/

Maximum Units on a Truck - LeetCode

 

• 1010. Pairs of Songs With Total Durations Divisible by 60 [Medium]

https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/

Pairs of Songs With Total Durations Divisible by 60 - LeetCode

 

 

• 17. Letter Combinations of a Phone Number [Medium]

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

Letter Combinations of a Phone Number - LeetCode

 

 

• 1041. Robot Bounded In Circle 

https://leetcode.com/problems/robot-bounded-in-circle/

Robot Bounded In Circle - LeetCode