리트코드 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(); }
'PS > PS Log' 카테고리의 다른 글
23.02.21. 풀었던 문제들 (0) | 2023.02.21 |
---|---|
23.02.20. 풀었던 문제들 (0) | 2023.02.20 |
23.02.18. 풀었던 문제들 (0) | 2023.02.18 |
23.02.17. 풀었던 문제들 (0) | 2023.02.17 |
22.09.08. 풀었던 문제들 (0) | 2022.09.08 |