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

 

주마다 문제 정리 없이 급하게 풀다 보니 문제풀이를 밀려버렸다..

이번 주에는 쭉 여태 풀었던 문제들을 정리할 예정이다.

 

문제 풀이 포스팅은 그냥 혼자 문제들 복기해보고 정리하기 위한 포스팅인데

300문제정도 풀면 알고리즘별 문제를 정리해서 도움이 되도록 포스팅 좀 해봐야겠다.

 

---

Tree 문제

 

• 101. Symmetric Tree [Easy]

 

https://leetcode.com/problems/symmetric-tree/

Symmetric Tree - LeetCode

 

바이너리 트리가 주어지면 루트를 기준으로 각각 subtree가 대칭구조인지 찾는 문제.

 

 

나는 stack을 이용해서 짜다보니 코드가 좀 복잡했었는데 그냥 recursive로 풀면 코드가 간단해진다.

 

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        
        stack<TreeNode*> s;
        
        if(!root)
            return true;
        
        if(!root->left && !root->right)
            return true;
        else if(!root->left || !root->right)
            return false;
        
        s.push(root->left);
        s.push(root->right);
        
        while(!s.empty()) {
            TreeNode* val_r = s.top();
            s.pop();
            TreeNode* val_l = s.top();
            s.pop();
            
            if (val_l->val != val_r->val)
                return false;
            
            if(val_r->right && val_l->left) {
                s.push(val_r->right);
                s.push(val_l->left);
            }
            else if(val_r->right || val_l->left) {
                return false;
            }
            
            if(val_r->left && val_l->right) {
                s.push(val_r->left);
                s.push(val_l->right);
            }
            else if(val_r->left || val_l->right) {
                return false;
            }
        }
        
        return true;
    }
};

 

 

• 98. Validate Binary Search Tree [Medium]

 

https://leetcode.com/problems/validate-binary-search-tree/

Validate Binary Search Tree - LeetCode

 

루트가 주어지면 해당 트리가 BST인지 아닌지 리턴해주는 문제

 

중위순회를 하면서 BST 조건을 만족하는지 확인하는 방식으로 풀었다.

아니 근데 이 문제는 왜 stack을 사용해 중위순회를 하면 속도가 recursive보다 겁나 떨어지는건지..? 💁🏻

 

다음에 recursive로 다시 풀어봐야할 문제....

 

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> s;
        
        int prev_val = 0;
        bool first = true;
        
        while(!s.empty() || root){
            while(root) {
                s.push(root);
                root = root->left;
            }
            
            root = s.top();
            s.pop();
            
            if(first) {
                first = false;
            }
            else if(prev_val >= root->val)
                return false;
            
            prev_val = root->val;
            root = root->right;
        }
        
        return true;
    }
};

 

 

• 127. Word Ladder [hard]

 

https://leetcode.com/problems/word-ladder/

Word Ladder - LeetCode

 

이 문제는.. 너무 어려웠다.. hard문제는 제대로 풀어본 적이 없다..

 

시작 단어와 끝 단어가 주어지고 단어 리스트가 주어진다.

시작 단어에서 딱 한 문자만 변경된 단어가 리스트에 있으면 넘어간다. 

이렇게 반복적으로 단어를 찾아가면서 끝 단어에 도달하면 길이를 return 해준다.

 

가능한 가장 짧은 길이를 리턴해줘야 하고 없으면 0을 리턴한다.

 

unordered_map도 사용해보고 여러 가지 방법을 사용해봤지만 실패 ^^!

 

discuss를 보니 문자를 하나씩 대치해가며 찾는다.

요런 방법도 있구나 배운 문제.. 

 

시간복잡도는 거의 O(len(word)^2 * len(dict)) 정도 된다.

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        
        unordered_set<string> dict(wordList.begin(), wordList.end());
        
        queue<string> q;
        q.push(beginWord);
        
        int result=1;
        
        while(!q.empty()) {
            int size = q.size();
            
            for(int q_size=0;q_size<size;q_size++) {
                string cur = q.front();
                q.pop();
                
                dict.erase(cur);
            
                if(cur.compare(endWord) == 0)
                    return result;

                for(int idx=0;idx<cur.size();idx++) {
                    char c = cur[idx];

                    for(int s=0;s<26;s++) {
                        cur[idx] = 'a'+s;

                        if(dict.find(cur) != dict.end()) {
                            q.push(cur);
                            dict.erase(cur);
                        }
                    }
                    cur[idx] = c;
                }
            }
            result++;
        }
        
        return 0;
    }
};

 

• 200. Number of Islands [medium]

https://leetcode.com/problems/number-of-islands/

Number of Islands - LeetCode

 

mxn grid가 주어지고 1은 land, 0은 water라고 했을 때 water로 둘러싸여진 land가 몇 개 있는지 리턴하는 문제

 

전형적인 dfs 문제이다.

 

처음에는 checked를 만들어서 확인한 곳과 안한 곳을 체크하며 돌았는데 TLE가 발생을...

그래서 그냥 확인한 곳은 0으로 만들어버렸다..ㅎㅎ

class Solution {
public:
    pair<int, int> fours[4] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
    
    void DFS(vector<vector<char>>& grid, int i, int j) {
        
        grid[i][j] = '0';
        
        for(int k=0;k<4;k++) {
            int new_i = i+fours[k].first;
            int new_j = j+fours[k].second;
            
            if(new_i < 0 || new_j < 0 || new_i >= grid.size() || new_j >= grid[0].size())
                continue;
            
            if(grid[new_i][new_j] == '1')
                DFS(grid, new_i, new_j);
        }
    }
    
    int numIslands(vector<vector<char>>& grid) {
        
        int numIsland=0;
        
        for(int i=0;i<grid.size();i++) {
            for(int j=0;j<grid[0].size();j++) {
                if(grid[i][j] == '1') {
                    numIsland++;
                    DFS(grid, i, j);
                }
            }
        }
        
        return numIsland;
    }
};

 

 

Linked List

 

• 2. Add Two Numbers

https://leetcode.com/problems/add-two-numbers/

Add Two Numbers - LeetCode

 

두 개의 링크드 리스트가 주어지면 각각 노드별로 더해주고 결과를 동일하게 리스트로 리턴해주는 문제

단, input으로 주어진 두 개의 링크드 리스트는 숫자가 거꾸로 저장되어 있다.

 

input이 처음부터 일의 자리 숫자 -> 십의 자리 숫자 -> 백의 자리 숫자 ... 로 저장되어 있기 때문에

그냥 각 자릿수 별로 더해서 노드 생성한 후 리턴해주면 된다.

 

여기서 고려해줘야 할 것은 5+5와 같이 자릿수가 올라갈 경우인데 

/와 % 연산을 잘 사용해주면 쉽게 해결이 가능하다.

 

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode(0);
        ListNode* cur = head;
        
        int saved_val = 0;
        while(l1||l2||saved_val) {
            int val=saved_val;
            if(l1) {
                val += l1->val;
                l1 = l1->next;
            }
            if(l2) {
                val += l2->val;
                l2 = l2->next;
            }
            
            cur->next = new ListNode(val%10);
            saved_val = val/10;
            
            cur=cur->next;
        }
        
        return head->next;
    }
};