23.02.28. 풀었던 문제들

Leetcode 652. Find Duplicate Subtrees

 tree 순회를 이용해 푸는 문제. 처음에는 leaf node부터 탐색하고, 이후에 올라오려 그랬다. 그러나 TreeNode struct에 parent를 가리키는 것이 없기 때문에 이렇게 풀 수 없었다.

 그러다 떠올린 게 string으로 순회하고 겹치는 부분을 찾으면 되는 것 아닌가?였다. 일단 preorder로 순회 결과를 쭉 적고 거기서 겹치는 걸 어떻게 찾을지 고민했다.

 그렇지만 이렇게 하면 너무 많은 탐색을 해야 한다. 그래서 고민하다 어떤 점부터 traverse 결과를 map에 넣어두면 똑같은 순회 결과가 몇개인지 알 수 있다를 생각했다.

 그리고 이 접근이 맞았다! value가 똑같을 수 있으니 left와 right를 구분해 주어야 하는 것만 빼면...

// Runtime 37 ms Beats 45.56%
// Memory 56.2 MB Beats 22.78%

class Solution {
public:
    map<string, TreeNode*> m;
    set<TreeNode*> answer;
    string preorder(TreeNode* v){
        string childsTraverseResult = "";
        childsTraverseResult += to_string(v->val);
        if(v->left != NULL) childsTraverseResult += "L" + preorder(v->left);
        else childsTraverseResult += "LN"; // 놓침 : null일 때 표기해 주어야 함 
        if(v->right != NULL) childsTraverseResult += "R" + preorder(v->right);
        else childsTraverseResult += "RN"; // 놓침 : null일 때 표기해 주어야 함

        // 순회가 끝나고 자신에게 돌아왔을 때, 똑같은 순회 결과가 있는지 검사
        if(m.find(childsTraverseResult) != m.end()){
            answer.insert(m[childsTraverseResult]);
        }
        else{
            m[childsTraverseResult] = v;
        }
        return childsTraverseResult;
    }
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        preorder(root);
        vector<TreeNode*> result(answer.begin(), answer.end());
        return result;
    }
};

 

시간복잡도

 map에 최대 O(n)개가 들어가므로 map 연산은 O(logn), DFS는 O(V + E)이지만 binary tree이므로 O(n). 따라서 O(nlogn)이다.

 

공간복잡도

 set에 worst case O(n)개 들어가고 map에도 똑같이 O(n)개 들어가므로 O(n)이다.

 

 

 개선할 수 없을까? set을 굳이 쓰지 않고, map에 count를 세서 0이면 map에 넣고, 1이면 answer에 넣고 map++, 2 이상일 땐 아무것도 하지 않아도 된다. map의 value값에도 굳이 TreeNode*를 넣을 필요가 없다. int를 넣고 조건을 만족할 때 v를 넣어주면 된다.

 n 값이 작으므로 unordered_map으로 하면 map 탐색에 O(1)이 걸리므로 O(n)에 풀린다.

 또한 DFS의 정석에 따라 종료조건을 v가 null일때로 명시해 보자. 

// Runtime 31 ms Beats 67.8%
// Memory 49.6 MB Beats 32%

class Solution {
public:
    unordered_map<string, int> m;
    vector<TreeNode*> answer;
    string preorder(TreeNode* v){
        if(v == NULL) return "";
        string childsTraverseResult = to_string(v->val);
        childsTraverseResult += "L" + preorder(v->left);
        childsTraverseResult += "R" + preorder(v->right);

        m[childsTraverseResult]++;
        if(m[childsTraverseResult] == 2){
            answer.push_back(v);
        }
        return childsTraverseResult;
    }
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        preorder(root);
        return answer;
    }
};

 

 

프로그래머스 혼자 놀기의 달인

 간단한 DFS 문제. 다만 문제의 특성 상 모든 vertex의 outgoing edge는 1이며, 모든 edge가 distinct한 것이 보장되기 때문에 한 vertex로 2개의 incoming edge가 올 수 없다. 따라서 cycle을 찾으면, 그 cycle 이외에서 오는 incoming edge가 없다는 것을 알 수 있기 때문에 cycle 탐색 + 크기를 찾고, 그것들을 정렬해서 계산만 하면 되는 문제.

int n;
bool visited[101];
vector<int> card;
vector<int> points;

void DFS(int cur, int point){
    if(visited[cur-1]){
        points.push_back(point);
        return;
    }
    visited[cur-1] = true;
    DFS(card[cur-1], point+1);
}

int solution(vector<int> cards) {
    n = cards.size();
    card = cards;
    
    for(int c : card){
        DFS(c, 0);
    }
    
    sort(points.begin(), points.end(), greater<int>());
    
    if(points[0] == n) return 0;
    return points[0] * points[1];
}

 

시간복잡도

 DFS이므로 O(V + E), 여기서는 E = V이므로 O(V)이다.

 

공간복잡도

 cards, points vector에 각각 n개씩을 넣으므로 O(n)

 

 

프로그래머스 테이블 해시 함수

 cmp 함수만 구현한다면 나머지는 indexing에 유의해서 구현하기만 하면 되는 문제이다.

 cmp를 구현할 때는, cmp의 인자가 2개뿐임에 유의해서 전역변수를 하나 사용하면 쉽게 풀 수 있다.

int standard;
bool cmp(vector<int>& a, vector<int>& b){
    if(a[standard-1] == b[standard-1]){
        return a[0] > b[0];
    }
    else return a[standard-1] < b[standard-1];
}

int solution(vector<vector<int>> data, int col, int row_begin, int row_end) {
    standard = col;
    sort(data.begin(), data.end(), cmp);
    vector<int> xors;
    for(int i = 0; i<data.size(); i++){
        int sum = 0;
        for(int value : data[i]){
            sum += value % (i+1);
        }
        xors.push_back(sum);
    }
    
    int answer = xors[row_begin-1];
    for(int i = row_begin; i<row_end; i++){
        answer ^= xors[i];
    }
    return answer;
}

 

 

프로그래머스 호텔 대실

 start time, end time이 주어질 때 최대로 겹치는 게 몇개인지 찾는 문제. 

 greedy 문제이며, 끝 시간을 오름차순 정렬 후 i+1부터 n까지 시작 시간이 i의 끝시간보다 작은 값들의 개수를 리턴하면 된다.

typedef pair<int, int> pii;

// 끝 시간 오름차순, 같으면 시작 시간 오름차순
bool cmp(pii &a, pii &b){
    if(a.second == b.second) return a.first < b.first;
    return a.second < b.second;
}

int solution(vector<vector<string>> book_time) {
    vector<pii> times; // .first : 시작 시간, .second : 끝나는 시간
    for(vector<string> v : book_time){
        int start = stoi(v[0].substr(0, 2)) * 60 + stoi(v[0].substr(3, 2));
        int end = stoi(v[1].substr(0, 2)) * 60 + stoi(v[1].substr(3, 2)) + 10;
        times.push_back({start, end});
    }
    sort(times.begin(), times.end(), cmp);
    
    int answer = -1;
    
    vector<int> startTimes;
    for(pii t : times){
        startTimes.push_back(t.first);
    }
    sort(startTimes.begin(), startTimes.end(), less<int>()); // 오름차순
    
    int n = times.size();
    for(int i = 0; i<n; i++){
        int endTime = times[i].second, cnt = 1;
        // 끝시간 오름차순 정렬, 다음 index의 시작시간이 그것보다 작은 값들의 max값
        for(int j = i+1; j<n; j++){
            if(times[j].first < endTime) cnt++;
        }
        answer = max(answer, cnt);
    }
    
    return answer;
}