23.03.11. 풀었던 문제들

프로그래머스 숫자 타자 대회

첫 접근

 첫 접근은 greedy였다. 각 탐색 시 왼손을 움직이는 경우와 오른손을 움직이는 경우 2개의 경우의 수가 있으므로 brute-force를 사용하면 $2^{100000}$이므로 가뿐하게 시간 초과가 난다. 따라서 greedy를 사용했다.

 

 dp[i][j] : 숫자 i를 손 i로 입력했을 때 최솟값으로 두고, j는 0 또는 1이다.

• dp[i][0](i번째 수를 왼손으로 누른 수) = min(이전에 왼손으로 누르고 또 왼손으로 누른 경우, 이전에 오른손으로 누르고 또 오른손으로 누른 경우)로 계산해
• dp[i][0] = min(dp[i-1][0] + weights[이전 왼손 위치][numbers[i]], dp[i-1][1] + weights[이전 왼손 위치][numbers[i]]
• 오른손도 똑같은 방식으로
•  dp[i][1] = min(dp[i-1][0] + weights[이전 오른손 위치][numbers[i]], dp[i-1][1] + weights[이전 오른손 위치][numbers[i]]

 이렇게 풀면 한 50점은 맞게 된다.

 

 그러나 이 경우 [두 손가락이 같은 칸에 있으면 안 된다]는 조건을 달성하지 못한다. 이것을 만족하기 위해서는

• 이번에 왼손으로 누르는 경우
  • 이번 수가 이전 수의 오른손에 있지 않아야 함. 오른손에 있다면 그 값 +1을 해주어야 함
• 이번에 오른손으로 누르는 경우
  • 이번 수가 이전 수의 왼손 위치에 있지 않아야 함. 왼손 위치에 있다면 그 값 +1을 해 주어야 함

이렇게 2개의 경우의 수가 더 생기게 된다. 총 2 * 2 * 2로 8개의 조건에 생기는데 그러면 if-else가 총 합쳐 8개가 되는 것이다. 이건 아니지 않나?

 

 

올바른 접근

 그래서 solution을 보고 힌트를 얻었다. bottom-up DP 말고 top-down 3차원 DP로 쉽게 풀 수 있다.

 

 dp[i][j][k]를 왼손은 j, 오른손은 k에 위치할 때 i번째 숫자부터 끝까지 누르는 최소값이라 정의하자.

 

 그러면

 

• base case : i == numbers.size()일 때 아무 숫자도 누르지 않아도 되므로 return 0
• 왼손을 움직이는 경우 dp[i][j][k] = dp[i+1][number[i]][k] + weights[numbers[i]][j]이다.
  
  • 풀어 설명하면,
  • 왼손은 j, 오른손은 k에 위치할 때 i번째 숫자부터 끝까지 누르는 최소값 = 
  • 왼손은 number[i], 오른손은 k에 위치할 때 i+1번째 숫자부터 끝까지 누르는 최소값 + j부터 number[i]까지 weight
  • 즉슨 왼손을 j에서 numbers[i]로 옮기고 누른 것이다.
• 오른손을 움직이는 경우 dp[i][j][k] = dp[i+1][j][number[i] + weights[numbers[i][k]이다.
  • 위와 같다.
  • 왼손은 j, 오른손은 k에 위치할 때 i번째 숫자부터 끝까지 누르는 최소값 = 
  • 왼손은 k 오른손은 number[i]에 위치할 때 i+1번째 숫자부터 끝까지 누르는 최소값 + k부터 number[i]까지 weight
  • 즉슨 오른손을 k에서 numbers[i]로 옮기고 누른 것이다.

 

 다만 [두 손가락이 같은 칸에 있으면 안 된다]는 조건을 달성하기 위해서는 아래 두 조건을 추가해야 한다.

• 왼손을 움직이는 경우 : 왼손을 움직였을 때 오른손 위치와 같아지면 탐색하지 않음
  • 즉슨 왼손을 움직였을 때 오른손 위치와 다를 때만 탐색
• 오른손을 움직이는 경우 : 오른손을 움직였을 때 왼손 위치와 같아지면 탐색하지 않음
  
  • 오른손을 움직였을 떄 왼손 위치와 다를 때만 탐색

 

 마지막으로 memoization을 한다.

// weights[i][j] : 숫자 i부터 j까지 가중치
vector<vector<int>> weights = {
    {1, 7, 6, 7, 5, 4, 5, 3, 2, 3}, // 0
    {7, 1, 2, 4, 2, 3, 5, 4, 5, 6}, // 1
    {6, 2, 1, 2, 3, 2, 3, 5, 4, 5}, // 2
    {7, 4, 2, 1, 5, 3, 2, 6, 5, 4}, // 3
    {5, 2, 3, 5, 1, 2, 4, 2, 3, 5}, // 4
    {4, 3, 2, 3, 2, 1, 2, 3, 2, 3}, // 5
    {5, 5, 3, 2, 4, 2, 1, 5, 3, 2}, // 6
    {3, 4, 5, 6, 2, 3, 5, 1, 2, 4}, // 7
    {2, 5, 4, 5, 3, 2, 3, 2, 1, 2}, // 8
    {3, 6, 5, 4, 5, 3, 2, 4, 2, 1}  // 9
};

int dp[100001][11][11]; // dp[i][j][k] : 왼손은 j, 오른손은 k에 위치할 때 i번째 숫자부터 끝까지 누르는 최소값
int INF = 987654321;
int len;
vector<int> Numbers;

void init(){
    for(int i = 0; i<=100000; i++){
        for(int j = 0; j<=10; j++){
            for(int k = 0; k<=10; k++){
                dp[i][j][k] = INF;
            }
        }
    }
}

int recurse(int i, int j, int k){
    if(dp[i][j][k] != INF) return dp[i][j][k]; // memoization
    if(i == len) return 0;
    
    // 왼손이 움직이는 경우 : 오른손 위치와 달라야함
    if(Numbers[i] != k){
        dp[i][j][k] = min(dp[i][j][k], recurse(i+1, Numbers[i], k) + weights[j][Numbers[i]]);
    }
    
    // 오른손이 움직이는 경우 : 왼손 위치와 달라야 함
    if(Numbers[i] != j){
        dp[i][j][k] = min(dp[i][j][k], recurse(i+1, j, Numbers[i]) + weights[k][Numbers[i]]);    
    }
    
    return dp[i][j][k];
}

int solution(string numbers) {
    len = numbers.size();
    init();
    Numbers.resize(len);
    for(int i = 0; i<len; i++){
        Numbers[i] = numbers[i] - '0';   
    }
    
    return recurse(0, 4, 6);
}

 

시간복잡도

 3차원 DP로 풀었다. memoization을 통해 있는 값인 경우 탐색하지 않으므로 3차원 size만큼 시간복잡도가 나온다. 10만 * 10 * 10 = 천만. 따라서 시간 내에 풀린다.

 

후기

 흐.. 3차원 DP는 몰랐다...

 처음 풀었던 greedy 직관이 맞은 것 같긴 한데 추가 조건이 붙음으로써 코드가 너무너무 복잡해졌다. 이런 PS 문제는 너무 복잡한 접근 말고 간단하게 풀린다는 것을 생각하고 너무 길어지면 다른 방법을 생각해 보자.

 

 

 

프로그래머스 등대

 문제를 보고, edge 개수가 n-1, vertex 개수가 n인 것에서 이 graph가 tree라는 것을 눈치챌 수 있어야 한다. 그리고 재미있는 특성 하나를 이용해 brute-force한다.

• parent가 색칠되어 있다면 child는 색칠되어 있지 않아도 된다.(색칠되어도 된다.)
• parent가 색칠되어 있지 않다면 child는 색칠되어 있어야 한다.

 이 특성을 이용해 leaf까지 DFS한다. DFS할 때 리턴값으로 [해당 vertex를 색칠했을 때 최소 색칠 회수, 해당 vertex를 색칠하지 않았을 때 최소 색칠 회수]를 리턴한다. 만약 leaf라면 [1, 0]이 될 것이다. 

• current가 색칠되어 있다면 child는 색칠되지 않아도 된다. 색칠되어도 된다. 따라서 childResult 값 중 min값을 가져온다.
• current가 색칠되어 있지 않다면 모든 child는 색칠되어야 한다. 따라서 childResult.first ( child가 색칠되었을 때 child를 root로 가지는 tree의 최소 색칠 회수 )를 더해 주어야 한다.

using namespace std;
typedef pair<int, int> pii;
vector<vector<int>> edges;
vector<bool> visited;

// .first : curV를 색칠했을 때 색칠 최소값
// .second : curV를 색칠하지 않았을 때 색칠 최소값
pii DFS(int curV){
    visited[curV] = true;
    
    pii cur = {1, 0}; // if leaf then return [1, 0]
    
    for(int adj : edges[curV]){
        if(!visited[adj]){
            pii childResult = DFS(adj);
            // curV를 색칠하지 않았다면 child는 색칠되어야만 함
            cur.second += childResult.first;
            // curV를 색칠했다면 child는 색칠되든 말든 상관없음
            cur.first  += min(childResult.first, childResult.second);
        }
    }
    
    return cur;
}

int solution(int n, vector<vector<int>> lighthouse) {
    // initialize
    edges.resize(n+1);
    for(vector<int> vi : lighthouse){
        edges[vi[0]].push_back(vi[1]);
        edges[vi[1]].push_back(vi[0]); 
    }
    visited.resize(n+1);
    fill(visited.begin(), visited.end(), false);
    
    pii result = DFS(1);
    
    return min(result.first, result.second);
}

 

시간복잡도

 DFS이므로 O(V + E)인데 E = n-1, V = n이므로 O(n)

 

후기

 문제가 너무 익숙해서 봤더니 예전에 풀었던 문제였다. 다만 풀이는 기억이 나지 않았는데 다시 봐도 신박하다.

 재귀를 이용한 top-down dp도 많이 익숙해 져야 할 것 같다... - subproblem으로 생각할 수 있어야 한다. dp같은 문제는 base case + 작은 문제로 쪼개어 생각하자.

 

 

 

LeetCode 109. Convert Sorted List to Binary Search Tree

 오름차순 정렬된 singly linked list를 balanced tree로 바꾸는 문제이다. 

 

첫 접근 : time O(n), space O(n)

 첫 접근은 singly linked list의 모든 element를 vector에 넣고 중간값을 parent에, 왼쪽 부분과 오른쪽 부분을 divide-and-conquer 하는 방식으로 구현헀다. T(n) = 2T(n/2) + O(1)이기 때문에 시간복잡도는 O(n)

// Runtime 22 ms Beats 92.11%
// Memory 28.4 MB Beats 47.40%

class Solution {
public:
    vector<int> arr;
    TreeNode* search(int start, int end){
        if(start > end) return NULL;
        int mid = (start + end) / 2;

        TreeNode *left = search(start, mid - 1);
        TreeNode *right = search(mid + 1, end);
        TreeNode *cur = new TreeNode(arr[mid], left, right);
        return cur;
    }

    TreeNode* sortedListToBST(ListNode* head) {
        // base case
        if(head == NULL) return NULL;

        // arr에 push : O(n)    
        while(head != NULL){
            arr.push_back(head->val);
            head = head->next;
        }

        // binary search : T(n) = 2T(n/2) + O(1) -> O(n)
        return search(0, arr.size()-1);
    }
};

 

 solution을 보니 개선할 수 있었다.

 

두번째 접근 : time O(nlogn), space O(logn)

 먼젓번 풀었던 142. Linked List Cycle II에서 했던 것처럼 slow pointer, fast pointer를 둔다. fast pointer는 한 번에 2칸씩, slow pointer는 한 번에 1칸씩 간다. fast pointer가 linked list의 끝에 다다른다면 slow pointer는 linked list의 중간에 다다랐을 것이다. 속도가 2배 차이이기 때문에...

 따라서 이 slow pointer를 middle treenode로 잡고 그 왼쪽 것과 오른 쪽 것으로 divide-and-conquer한다. 다만 이 때 slow pointer 한 칸 앞에 있는 것->next를 NULL로 끊어 주어야 한다. 그래야 divide가 된 것이기 때문에. 이 부분은 slowPrev라는 변수를 이용해 구현했다.

 divide-and-conquer는, 만약 위 탐색법으로 가져온 element와 head가 같은 경우 더 이상 탐색하지 않아야 한다. 만약 더 탐색하면 무한루프가 걸려버리기 때문에 종료 조건을 하나 걸어 주어야 한다. 이후 head -> mid 직전 / mid 직후 -> 끝까지 이렇게 2개의 linked list로 동일한 탐색을 하고 TreeNode의 left child, right child에 붙여주면 된다.

 

 공간복잡도는, 추가 공간을 사용하지 않기 때문에 O(1)이지만 divide-conquer하는 과정에서 총 logn번 함수가 호출되므로 O(logn)이다. 시간복잡도는 T(n) = 2T(n/2) + O(n)이므로 O(nlogn)이다.

// Runtime 22 ms Beats 92.11%
// Memory 28.3 MB Beats 92.35%

class Solution {
public:
    ListNode* getMiddlePointer(ListNode* head){
        // slowPrev : slow 이전의 vertex
        // slow : 1칸씩 감
        // fast : 2칸씩 감
        ListNode *slowPrev = head, *slow = head, *fast = head;
        while(fast != NULL && fast->next != NULL){
            slowPrev = slow;
            fast = fast->next->next;
            slow = slow->next;
        }
        if(slowPrev != NULL) slowPrev->next = NULL;

        return slow;
    }

    TreeNode* sortedListToBST(ListNode* head) {
        // base case
        if(head == NULL) return NULL;

        ListNode *mid = getMiddlePointer(head);

        TreeNode *treeMid = new TreeNode(mid->val);
        if(head == mid) return treeMid; // 종료 조건을 명시하지 않는다면 계속 탐색하게 됨
        
        treeMid->left = sortedListToBST(head);
        treeMid->right = sortedListToBST(mid->next);

        return treeMid;
    }
};

 

 또 한번의 개선이 가능하다. 바로 위에서 시간복잡도에 영향을 주었던 것은 middle pointer를 찾는 부분이었다. 이 부분을 O(1)로 해결할 수 있다면? 방법이 놀랍게도 있다.

 

 

세 번째 접근 : time O(n), space O(logn)

 linked list의 middle pointer를 구하는 데 O(n) time을 썼기 때문에 이를 향상시켜야 한다. middle pointer를 어떻게 구할 수 있을까? solution은 curNode 변수를 하나 새로 두고 inorder 탐색을 하는 트릭으로 이를 만든다.

 left를 탐색하고, curNode를 탐색하고, curNode ++하고, right를 탐색한다. 이렇게 하는데 어떻게 curNode가 해당 tree의 middle pointer를 가리킬 수 있을까?

 

 이 트릭 자체가 curNode가 middle pointer를 가리키게 한다.

•  base case부터 생각해 보자. size가 1일 때는 curNode가 무조건 가운데이므로 참이다.
•  size가 2일 때, left를 탐색하고 curNode++를 하면 curNode는 다음 vertex를 가리킨다. 참이 된다.
•  size가 3이면, left를 탐색하고 curNode++되기 때문에 curNode가 다음 vertex 즉 middle을 가리키게 된다.
•  ...

 위 pseudo code를 따르면 left를 탐색하고, 이후 curNode++하고, 이후 right를 탐색한다. leaf node에 다다르면 자신의 것을 탐색하고 curNode++한다. 즉... 알고리즘의 구성에 의해 [left 탐색 회수]만큼 [curNode++ 연산]이 이루어진다. [left vertex 개수]만큼 [curNode++]된다는 것이다. 따라서 left 탐색 이후에 curNode가 middle pointer임을 보장할 수 있다. 별 신기한 트릭이 다 있다.

// Runtime 19 ms Beats 97.30%
// Memory 28.3 MB Beats 92.35%

class Solution {
public:
    ListNode *curNode; // curNode라는 변수가 middle pointer가 된다.
    int size = 0; // linked list size
    
    // attribute initialize
    void init(ListNode* head){
        this->curNode = head;
        while(head){
            head = head->next;
            this->size++;
        }
    }

    TreeNode* DFS(int start, int end){
        // base case. 범위가 벗어나지거나 curNode가 null인 경우 리턴
        if(start > end || this->curNode == NULL) return NULL;

        int mid = (start + end) / 2;
        
        // 1. left를 DFS한다.
        TreeNode *treeLeft = DFS(start, mid-1);

        // 2. curNode가 tree의 middle pointer가 된다. 따라서 curNode로 tree pointer를 만든다.
        TreeNode *treeMid = new TreeNode(curNode->val);
        
        // 3. curNode++한다.
        this->curNode = this->curNode->next;

        // 4. right를 DFS한다.
        TreeNode *treeRight = DFS(mid + 1, end);

        // 5. left, right DFS 결과를 tree middle에 붙여넣고 리턴한다.
        treeMid->left = treeLeft;
        treeMid->right = treeRight;

        return treeMid;
    }

    TreeNode* sortedListToBST(ListNode* head) {
        // base case
        if(head == NULL) return NULL;
        init(head);

        return DFS(0, this->size-1);
    }
};

 

 

후기

 많은 개선을 통해 time O(n), space O(logn)으로 문제를 풀 수 있었다. 놀랍다... 일반적으로 알고리즘 문제는 memory보다 time이 더 중요하기 때문에 두 번째 접근보다는 처음 푼 접근이 더 좋을 것 같다. 그러나 면접 때 물어본다면 세 번째 접근까지는 몰라도 두 번째 접근까지는 할 수 있어야 할 것 같다.

 사실 두 번째 접근도 그리 간단한 접근은 아니다. fast, slow 2개의 pointer로 속도차를 이용해 linked list에서 무언가를 구하는 발상이 쉽진 않으니까.. 그래도 앞으로 linked list가 나오면 slow, fast poiner를 사용할 건덕지가 없는지 생각해 봐야 겠다.