짱아의 개발 기록장

마찬가지로, 트리를 기반으로 한 BFS문제이다. [메인 로직] queue를 pair형태로 다음과 같이 자료구조를 짰다. => queue q; second 위치에 dir변수를 두어서 dir==-1일 경우 거꾸로 저장하도록 했다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647class Solution {public: vector zigzagLevelOrder(TreeNode* root) { vector ans; if(root==NULL){ return ans; } vector v; queue q; q.push(make_pair(root, 1)); while(!q.empty()){ int size = q..

BFS를 통해서 간단하게 해결할 수 있는 문제이다. [메인 로직] 간단히 말해서, 같은 level에 있는 값들을 하나의 벡터에 넣어주고 그것을 다시 최종 ans벡터에 넣어주는??? 그런 로직이다. 코드를 보면 더 잘 이해가 될 것이라 생각한다. 1234567891011121314151617181920212223242526272829303132333435class Solution {public: vector levelOrder(TreeNode* root) { vector ans; if(root==NULL){ return ans; } vector v; queue q; q.push(root); while(!q.empty()){ int size = q.size(); for(int i=0; ival); q.pop..

난이도는 easy였지만...생각보다? 이런 문제류를 처음 풀어본 사람이면 충분히 어려웠을 만한 문제였다. 분류로는 BFS로 되어 있었지만,,, 생각보다 간단한 재귀로 풀 수 있다. [메인 로직] 1. 주어진 root 트리를 각각의 다른 트리라고 생각하고 2개의 트리를 비교하는 형식으로 진행한다. 2. 즉, isMirror(root, root) 함수를 돌아서 tree1->left와 tree2->right이 같은지, tree1->right과 tree2->left가 같은지 확인하면 된다! (Symmetric인지 확인한는 것이기 때문에 => 밑의 사진 참고) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public: bool isMirror(TreeNode* tree..

아주 간단하게 재귀 방식을 통해서 풀 수 있는 문제였다. [메인 로직] 기본적으로 재귀를 root->left->right 순서로 PreorderTraversal을 진행했다. 1. 각 트리의 노드가 둘 다 NULL일 경우, true를 반환한다.(루트의 경우 NULL이면 어차피 left, right으로 뻗어가는 가지가 아니기 때문에 같은 형태임을 알 수 있다.) 2. 각 트리의 노드가 둘 중 하나만 NULL이라면, 같은 구조의 트리가 아니므로 false를 반환한다. 3. 각 트리의 노드의 값이 다르다면, 노드의 값이 다르므로 false를 반환한다. 4. 이후, 왼쪽 서브트리, 오른쪽 서브트리로 순환한다. 1 2 3 4 5 6 7 8 9 10 11 class Solution { public: bool isSa..

dfs중에서도 hard난이도에 해당되는 문제이다. Tree문제인데, BST의 두 노드가 바뀐 상태로 입력이 주어져질 때, structure을 바꾸지 않고 recovery하면 된다. 솔직히 InorderTraversal 후 모든 두 개의 값을 reverse해주고 오름차순으로 정렬되는 지 BruteForce로 일일히 확인하는 그런 방법 밖에 생각이 나지 않아서.... 다른 외국 유투버의 풀이방법을 참고했다. 간단한 로직은 다음 사진으로 첨부했다. 사진 그대로 1) 역전되는 곳이 1pair 생긴다면, 첫 번째 값을 first로, 두 번째 값을 second로 간주했다. 2) 역전되는 곳이 2pair 생긴다면, 첫 번째 pair의 첫 번째 값을 first로, 두 번째 pair의 두 번째 값을 second로 간주했..

dfs와 트리를 결합한 문제이다. Binary Search Tree의 특징에 대해 잘 이해하고 Tree의 Traversal이 어떻게 이루어지는 지 잘 이해하고 있으면 쉽게 풀이할 수 있다. [메인 로직] root->left, root->val, root->right순으로 dfs를 진행했다. 즉, Inorder Traversal을 통해 문제를 해결했다. 여기서 핵심은, BST의 경우 Inorder Traversal을 했을 때에 모든 값들이 오름 차순 정렬이 되어 있어야 한다는 것이다! root->val값들을 모두 vector에 저장해놓은 후, v[v.size()-1]의 값과 비교하여 이 값보다 작다면 무조건 false를 반환하도록 했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16..

오랜만에 dfs문제를 풀고 싶어서 LeetCode에서 dfs태그로 들어갔다. 재밌는 문제가 많아보였지만 역시 첫 번째 문제부터 들어갔다. 간단하게 dfs 재귀 방식으로 풀 수 있었다. [메인 로직] vector에 2~9까지의 idx에 각각 해당되는 문자를 넣어주었고 dfs로 digits에 해당되는 문자를 하나씩 탐색했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 class Solution { public: vector ans; vector phone[11]; void dfs(string digits, int idx, string..

생각보다 이런 유형의 문제들이 여러 기업들의 코딩테스트에 많이 출제된다. 거의 대부분 이런 문제들은 투포인터로 푸는 것이 시간복잡도를 줄일 수 있는 현명한 방법이다. 물론, Brute Force로 풀 수 있겠지만... O(n^2)이면 크기에 따라 Time Limit이 찍힐 수도 있다. LeetCode의 경우 C++기준으로 Time Limit이 뜬다. 투포인터 시간복잡도 : O(n) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 // Two-pointer class Solution { public: int maxArea(vector& height) { // 어차피 짧은 높이에 의해 넓이가 결정되기 때문에 // 맨끝 양쪽에서 ..