23.02.19. 풀었던 문제들

리트코드 daily challenge - 103. Binary Tree Zigzag Level Order Traversal

 Binary Tree를 BFS를 써서 순회하는 문제. 처음 풀었을 때는 7ms(27.9%), 12.2MB(17.21%)가 나왔다. 왜 이렇게 많이 나왔을까.. 생각해 보고, 답안지를 보고 개선점을 생각했다. 개선점은 아래 코드에 주석으로 달아놓았다.

typedef pair<TreeNode*, int> pni; // 개선

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        int maxDepth = -1;
        vector<vector<int>> answer;

        // BFS init
        queue<pni> q;
        q.push({root, 0});

        while(!q.empty()){
            // pop
            TreeNode* curNode = q.front().first;
            int curDepth = q.front().second;
            q.pop();
            if(curNode == NULL) continue;

            // if depth is deeper, than add
            if(curDepth > maxDepth){
                answer.push_back({});
                maxDepth = curDepth;
            }
            answer[curDepth].push_back(curNode->val);

            q.push({curNode->left, curDepth + 1});  // 개선
            q.push({curNode->right, curDepth + 1}); // 개선
        }

        for(int i = 1; i<answer.size(); i += 2){
            reverse(answer[i].begin(), answer[i].end());
        }
        return answer;
    }
};

 

 생각해 보면, child가 null인데 굳이 queue에 넣을 필요가 없다. 모든 경우에 대해 한 단계 더 탐색하는 것이기 때문에 이것만 줄여도 시간은 50% 감소할 것이라 생각하고, 개선했다. 개선한 코드는 아래와 같다.

 실행시간은 0ms(100%), 12.1MB(78.56%)이다. 필요없는 탐색으로 실행시간을 많이 줄였다. 여기서 메모리는 어떻게 더 개선할 수 있을까? 나는 pni라는 pair를 통해 현재 탐색하고 있는 vertex가 몇 번째 layer의 vertex인지 기록을 했다. 그러나 이렇게 할 필요가 없다! while문 안에 q.size()와, 반복문을 이용하면 이번에 탐색할 layer의 크기를 알아낼 수 있기 때문이다. 

typedef pair<TreeNode*, int> pni;

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if(root == NULL) return {}; // 개선한 부분

        int maxDepth = -1; // 개선
        vector<vector<int>> answer; 

        // BFS init
        queue<pni> q;
        q.push({root, 0});

        while(!q.empty()){
            // pop
            TreeNode* curNode = q.front().first;
            int curDepth = q.front().second;
            q.pop();
            if(curNode == NULL) continue;

            // if depth is deeper, than add
            if(curDepth > maxDepth){ // 개선
                answer.push_back({});
                maxDepth = curDepth;
            }
            answer[curDepth].push_back(curNode->val);

            if(curNode->left != NULL) q.push({curNode->left, curDepth + 1});   // 개선한 부분
            if(curNode->right != NULL) q.push({curNode->right, curDepth + 1}); // 개선한 부분
        }

        for(int i = 1; i<answer.size(); i += 2){
            reverse(answer[i].begin(), answer[i].end());
        }
        return answer;
    }
};

 

 메모리 사용량도 개선한 코드는 아래와 같다. 0ms(100%), 11.9MB(93.95%)이다.

 위에서 설명한 것과 같이, while문 내에 q.size()가 [이번에 탐색할 layer의 vertex 개수]임을 알 수 있고, for문을 사용해서 "지금 탐색 중인 vertex가 어떤 layer인지" 알 수 있다. 이걸 안다면? 현재 layer가 짝수인지, 홀수인지 알 수 있기 때문에 zig-zag도 판단해 넣을 수 있다.

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if(root == NULL) return {};

        vector<vector<int>> answer;
        bool isLeftToRight = true;

        // BFS init
        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty()){
            int curDepthSize = q.size(); // 개선한 부분
            vector<int> curDepthLayer(curDepthSize);

            for(int i = 0; i<curDepthSize; i++){ // 개선한 부분 - 이 for문으로 현재 layer vertex 개수를 알 수 있다.
                // pop
                TreeNode* curNode = q.front();
                q.pop();
                if(curNode == NULL) continue;

                int idx = isLeftToRight ? i : curDepthSize - i - 1;
                curDepthLayer[idx] = curNode->val;

                if(curNode->left != NULL) q.push(curNode->left);
                if(curNode->right != NULL) q.push(curNode->right);
            }

            isLeftToRight = !isLeftToRight;
            answer.push_back(curDepthLayer);
        }

        return answer;
    }
};

 

 i번째 layer의 개수를 3줄의 코드로 알아낸 것 같은 느낌이다. 상당히 좋은 기법인 듯 싶다.

 

프로그래머스 lv.1 과일 장수

 내림차순 정렬 하고, i번째 것만 구해주면 되는 쉬운 규칙 찾기 문제

 

프로그래머스 lv1 명예의 전당 (1)

 multiset을 이용해 정렬을 유지하고, iterator를 사용해 몇 칸 옮기는 문제. iterator는 advance를 이용한다.

 

프로그래머스 lv1 숫자 짝꿍

 vector로 각 숫자의 개수를 counting하고, string이 "00000"일 때만 예외처리 해 주면 되는 문제.

 

프로그래머스 lv1 문자열 나누기

 항상 귀찮은, C++ string parsing 문제.

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
    vector<string> answer;
    
    for(int i = 0; i<s.length(); i++){
        int si = i, count = 0; // si : 시작 index, count : 동일문자 개수
        char standard = s[si]; // 시작 index에 있는 문자
        while(i < s.length()){ // 범위 내에 있을 때
            if(s[i] == standard) count++;
            else count--;
            if(count == 0) break;
            i++;
        }
        answer.push_back(s.substr(si, i-si+1));
    }
    
    return answer.size();
}