23.02.27. 풀었던 문제들

리트코드 daily challenge - 427. Construct Quad Tree

 전형적인 DFS 탐색 문제. 종료 조건을 잘 명시하면 쉽게 풀 수 있다. 

// Runtime 12 ms Beats 86.96%
// Memory 15.7 MB Beats 66.30%

/*
// Definition for a QuadTree node.
class Node {
public:
    bool val;
    bool isLeaf;
    Node* topLeft;
    Node* topRight;
    Node* bottomLeft;
    Node* bottomRight;
    
    Node() {
        val = false;
        isLeaf = false;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }
    
    Node(bool _val, bool _isLeaf) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }
    
    Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
};
*/

class Solution {
public:
    Node* DFS(int r, int c, int len, vector<vector<int>>& grid){
        bool isAllSame = true; int standard = grid[r][c];
        for(int i = r; i<r+len; i++){
            for(int j = c; j<c+len; j++){
                if(grid[i][j] != standard){
                    isAllSame = false;
                    i = r+len; j = c+len;
                }
            }
        }

        // exit condition
        if(isAllSame){
            Node* cur = new Node(grid[r][c], 1); // val: grid[r][c], isLeaf: true
            return cur;
        }

        // deeper
        Node* cur = new Node(0, 0); // val: any, isLeaf: false
        int halflen = len/2;
        cur->topLeft = DFS(r, c, halflen, grid);
        cur->topRight = DFS(r, c + halflen, halflen, grid);
        cur->bottomLeft = DFS(r + halflen, c, halflen, grid);
        cur->bottomRight = DFS(r + halflen, c + halflen, halflen, grid);
        return cur;
    }

    Node* construct(vector<vector<int>>& grid) {
        return DFS(0, 0, grid.size(), grid);
    }
};

/*
leaf가 아닐 때 value를 t/f로 설정 가능
val : true then 1, else then 0
평범한 DFS 문제
*/

시간복잡도 & 공간복잡도

 T(n) = $n^{2}$ + 4T(n/2)이다. master theorem에 서 a = 4, b = 2, f(n) = $n^{2}$이다. 따라서 $O(n^{2}logn)$이다. 각 탐색에서, 모든 grid를 탐색하는 데 이걸 logn번 한다.

 공간복잡도는 size 1짜리가 $n^{2}$개, 4짜리가 $n^{2} / 2^{2}$개, ... k = logn^logn까지니까, $O(n^{2}logn)$이다.

 

 개선할 수는 없을까? 다른 사람들의 코드를 보았다.

class Solution {
public:
    Node* baseNode[2];
    Node* DFS(int r, int c, int len, vector<vector<int>>& grid){
        // base case
        if(len == 1) return baseNode[grid[r][c]]; // val : grid[r][c], isLeaf: true

        // deeper
        int halflen = len/2;
        Node* topLeft = DFS(r, c, halflen, grid);
        Node* topRight = DFS(r, c + halflen, halflen, grid);
        Node* bottomLeft = DFS(r + halflen, c, halflen, grid);
        Node* bottomRight = DFS(r + halflen, c + halflen, halflen, grid);

        // if all child has same value, then current must be leaf
        if(topLeft->isLeaf && topRight->isLeaf && bottomLeft->isLeaf && bottomRight->isLeaf && topLeft->val == topRight->val && topRight->val == bottomLeft->val && bottomLeft->val == bottomRight->val){
            return baseNode[grid[r][c]]; // val: grid[r][c], isLeaf: true
        }
        else{
            return new Node(1, 0, topLeft, topRight, bottomLeft, bottomRight);
        }
    }

    Node* construct(vector<vector<int>>& grid) {
        baseNode[0] = new Node(0, 1); // value 0, leaf node
        baseNode[1] = new Node(1, 1); // value 1, leaf node
        return DFS(0, 0, grid.size(), grid);
    }
};

 이렇게 작성했다. 

 

시간복잡도 & 공간복잡도

 T(n) = 4T(n/2)이다. master theorem에 서 a = 4, b = 2, f(n) = $O(1)$이므로 k=0이다. 따라서 $O(n^{2})$이다. 공간복잡도는 동일하다.

 

 그런데 막상 돌리면 오히려 더 늦어졌다. 문제 조건은 작은데, if문에 너무 많은 값을 검사해서 그런 것 같다.

 

 

프로그래머스 숫자 카드 나누기

 최대공약수를 잘 활용하면 풀리는 문제. 나는 좀 돌아돌아 풀었다..

• A, B의 GCD를 구한다.
  • A의 GCD가 B를 나눌 수 없는 경우 -> 정답 후보
  • B의 GCD가 A를 나눌 수 없는 경우 -> 정답 후보
  • 왜냐하면, A의 GCD는 모두 A를 나눌 수 있는 제일 큰 수이며, 이게 B를 나누지 못하는 경우가 최대이기 때문.
    • 나는 GCD의 약수까지 계산했는데, 그럴 필요가 없다. GCD의 약수인데 다른 array를 나누지 못하는 경우가 없기 때문이다. 오히려 나누면 나눴지.
• 헷갈린다.

int gcd(int a, int b){
    while(b != 0){
        int r = a%b;
        a = b;
        b = r;
    }
    return a;
}

int solution(vector<int> arrayA, vector<int> arrayB) {
    // get GCD of A's and B's
    int AGCD = arrayA[0];
    for(int i = 1; i<arrayA.size(); i++){
        AGCD = gcd(AGCD, arrayA[i]);
    }
    
    int BGCD = arrayB[0];
    for(int i = 1; i<arrayB.size(); i++){
        BGCD = gcd(BGCD, arrayB[i]);
    }
        
    bool Adividable = false;
    for(int a : arrayA){
        if(a % BGCD == 0) Adividable = true;
    }
    bool Bdividable = false;
    for(int b : arrayB){
        if(b % AGCD == 0) Bdividable = true;
    }    
    
    int answer = 0;
    if(!Adividable) answer = max(answer, BGCD);
    if(!Bdividable) answer = max(answer, AGCD);
    
    return answer;
}

 

 

프로그래머스 마법의 엘리베이터

 자리수에 따라 판정을 다르게 해 줘야 하는, 생각보다 까다로운 문제. 문제를 읽으면 알 수 있지만 5보다 크면 올림해서 내리는 게 이득이고, 반대는 그대로 두는 것이 이득이라는 것을 직관적으로 알 수 있다.

 그러나, 현재 자리가 5일 때는 다음 숫자에 따라 결정된다.

• 다음 숫자가 5~9라면 현재 자리값을 10에 가까워지도록 올림하는 게 이득이다.
• 다음 숫자가 0~4라면 현재 자리값을 0에 가까워지도록 내림하는 게 이득이다.
  • 555를 생각해 보자. 555의 최적 값은 14이다. 555 - 560(+5) - 600(+4) - 1000(+4) - 0(+1)
  • 55에서 첫 자리수는 5, 다음 자리수는 5이다. 현재 자리수를 10에 가까워지도록 올리면 5번의 연산으로 60이 된다. 다음 자리 수까지 거리가 1 줄게 된다. 그러나 0에 가까워지도록 하면 5번의 연산으로 50이 되고, 5로, 변하지 않는다.

 항상 edge case, 경계선에 있는 것을 위주로 생각하자.

int solution(int storey) {
    int answer = 0;
    string str = to_string(storey);
    reverse(str.begin(), str.end());
    storey = stoi(str);
    
    while(storey != 0){
        int cur = storey % 10; storey /= 10;
        int next = storey % 10;
        
        answer += min(abs(10 - cur), cur);
        if(cur > 5){ // 5보다 크면 한자리 올리는 게 이득
            storey += 1;
        }
        else if(cur < 5){
        }
        else{ // cur == 5
            if(next >= 5) storey += 1;
        }
    }
    
    return answer;
}