리트코드 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) = + 4T(n/2)이다. master theorem에 서 a = 4, b = 2, f(n) = 이다. 따라서 이다. 각 탐색에서, 모든 grid를 탐색하는 데 이걸 logn번 한다.
공간복잡도는 size 1짜리가 개, 4짜리가 개, ... k = logn^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) = 이므로 k=0이다. 따라서 이다. 공간복잡도는 동일하다.
그런데 막상 돌리면 오히려 더 늦어졌다. 문제 조건은 작은데, 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; }
'PS > PS Log' 카테고리의 다른 글
23.03.01. 풀었던 문제들 (0) | 2023.03.01 |
---|---|
23.02.28. 풀었던 문제들 (0) | 2023.02.28 |
23.02.26. 풀었던 문제들 (0) | 2023.02.26 |
23.02.25. 풀었던 문제들 (0) | 2023.02.25 |
23.02.24. 풀었던 문제들 (0) | 2023.02.24 |