Apes Together Strong.

https://leetcode.com/problems/kth-largest-element-in-an-array/description/ 주어진 정수 배열에서 k 번째로 큰 수를 찾아라. k번째로 큰 수는 minPriority Queue 에 배열을 넣고, 큐 사이즈가 k 가 될때까지 큐를 pop한다. 그리되면 사이즈 k 보다 작은 값들은 pop되고 k 개수 만큼 큰 값들만 남게 된다.  그 중 top이 k 번째로 큰 값이 된다.  코드 int findKthLargest(vector& nums, int k) { priority_queue, greater > minPQ; for (int q = 0; q k) minPQ.pop(); return minPQ.top();}   결과

https://leetcode.com/problems/k-closest-points-to-origin/description/ 2차원의 정점 정보가 주어질 때 원점에서 k 번째까지 가까운 점들을 찾아라.  priory queue를 구성할 줄 안다면 어렵지 않은 문제.  거리, index의 pair data로 queue를 구성해야 한다. 다만 여기서 거리는 크기의 비교로만 쓰이므로, root 연산은 해지 않아도 된다.(정확할 필요가 없다) 코드더보기vector> kClosest(vector>& points, int k) { priority_queue, vector>, greater>> pq; for (int q = 0; q > vRet; for (int q = k; q > 0; --q) ..

https://leetcode.com/problems/last-stone-weight/description/ 주어진 정수 배열은 돌의 무게을 의미한다. 가장 무거운 두개를 서로 부딪힌다. 무게가 같으면 사라진다. 다르면, 그 차가 남는다.  마지막 남은 돌의 무게를 구하라. 이거는 easy 난이도가 맞다. 직관대로 풀어 준다.  코드 더보기int lastStoneWeight(vector& stones) { priority_queue pqBuff; for (int q = 0; q = 2) { int first = pqBuff.top(); pqBuff.pop(); int second = pqBuff.top(); pqBuff.pop(); if (first ..

https://leetcode.com/problems/kth-largest-element-in-a-stream/description/정수형 입력 데이터가 주어질 때, k 번째로 큰 값을 반환하도록 하라. 조금 함정이 있는 문제다. 데이터가 얼마나 있는지, 다른 데이터는 무엇인지, 사실 문제는 관심없다. 오로지 반환으로 원하는 것은 k 번째 큰 값이다.  우선 map 등의 정렬된 hash등으로 값을 가질 수 있다.모든 값이 보존되며, add 시 정렬로 인해, O(logN) 시간이 소요 된다. 하지만 검색 시도 O(logN)이 소요된다. ( O(1) 을 원하면 hash_map 을 써야 하지만, 정렬이 지원되지 않는다. )이것으로도 충분히 문제는 풀릴 것이다.  다음으로 priority queue를 생각해 볼..

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/ Preorder와 Inorder traverse  정보가 주어질 때, 전체 tree를 구성하라. 우선 InOrder와 PreOrder에 대해 다시 정리할 필요가 있다.  DFS 그 순서 그대로 tree를 접근한다면, PreOrder 방식이라고 할 수 있다.어느 노드의 child를 어떤 식으로 attach하는지 정보를 얻기 위해 InOrder가 필요하다. inOrder는 이 값들을 tree의 밸런스 정보와 함께 가지고 있다. 즉, 특정 값이 inOrder에 존재 한다면, inOrder에서 해당 값보다 작은 index는 왼쪽 트리..

https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/ 주어진 tree에서 k 번째로 작은 값을 찾아 반환하라.  2진트리에서 InOrder traverse가 기본적으로 정렬을 의미함을 이해 한다.  따라서 InOrder traverse했을 때, k 번째로 접근하는 node 값을 찾으면 된다.  코드 더보기bool kthSmallestInOrder(TreeNode* node, int& k, int& outValue){ if (node == nullptr) return false; if (kthSmallestInOrder(node->left, k, outValue)) return true; ..

https://leetcode.com/problems/validate-binary-search-tree/description/ 주어진 tree가 유효한 이진 트리인지 판단하라. 우선 이진 트리에 조건을 생각해 볼 필요가 있다. 위 그림처럼, node값은 늘, left 와 right 의 사이 값을 가져야 한다.이 문제가 child 가 생기면 복잡해 진다. 위 그림처럼, 노드에서 조건을 만족해도 전체 트리에서는 만족하지 않게 될 수 있다. 즉, 정리하면 특정 노드 기준으로 left node 중 최대값, right node 중 최소값 사이에 노드값이 존재해야 한다. 따라서 특정 노드에서 모든 차일드 노드를 순회해서 left의 최대값, right의 최소값 을 구한 후 현재 노드가 이 값 사이에 있나 확인한다. ..

https://leetcode.com/problems/count-good-nodes-in-binary-tree/description/ 주어진 Binary Tree에서 good node의 수를 찾아라. good node는 root와 해당 노드 사이에 자신보다 큰 수가 없어야 한다. 특정 노드를 기준으로 root와 자신 사이에 max value를 구한다. 이 값이 node->val 보다 같거나 작으면 조건을 만족하는 것이다.  노드의 중복 탐색을 피하기 위해 자신을 포함하여 max value를 재 계산하고 다시 child로 내려가 조건 검사를 이어 간다.  코드 더보기void goodNodesHelper(int& cnt, int maxV, TreeNode* node){ if (node == nullpt..

https://leetcode.com/problems/binary-tree-right-side-view/description/ 주어진 tree의 각 level의 마지막 값을 구하라.   level order traversal을 한 후 제일 마지막 값만을 취한다. 코드더보기vector rightSideView(TreeNode* root) { vector vRet; if (root == nullptr) return vRet; queue qBuff; qBuff.push(root); while (qBuff.size() > 0) { int cnt = qBuff.size(); for (int q = 0; q val); ..

https://leetcode.com/problems/binary-tree-level-order-traversal/description/ 주어진 binary tree를 level order 탐색하라. 사실상 easy 난이도 문제.BS의 기본 문제, 다른 문제들로 응용에 잘 나옴.  코드 더보기vector> levelOrder(TreeNode* root) { vector> vRet; if (root == nullptr) return vRet; queue qBuff; qBuff.push(root); while (qBuff.size() > 0) { vector vBuff; int cnt = qBuff.size(); for (in..