Apes Together Strong.

https://leetcode.com/problems/invert-binary-tree/description/ 주어진 binary tree를 그림과 같이 역전시켜라. 쉬워 보이지만, 접근을 잘 해야 하는 문제.  제일 하단 leaf 노드부터 뒤집으면 그 위로 차례로 뒤집으면 해결됨을 파악해야 한다. 각 depth 별로 노드를 얻어 하려고 하면 복잡해 지고, DFS방식으로 접근해서 하단부터 값을 얻고 위로 올라오면서 적용한다.  코드 TreeNode* invertTree(TreeNode* node){ if (node == nullptr) return nullptr; auto left = invertTree(node->left); auto right = invertTree(nod..

https://leetcode.com/problems/merge-k-sorted-lists/description/ 다수의 정렬된 list가 주어질 때, 모든 정렬을 유지하면서 이 list를 하나로 merge 하라. 정렬이 되어 있으므로, 각 list의 제일 앞 node를 비교하며 제일 작은 순서대로 새 노드에 연결하면 될 것이다.  매번 모든 앞 노드를 비교하면서 최소 값을 가진 노드를 찾을 수 있고, 이것은 시간이 많이 걸릴 것이다. 혹은 추가되는 노드만 더하면서 정렬할 수도 있겠다. map 이나 priority queue를 사용하면 될 것 같다.  코드 더보기void pushNode(map>& mNodes, ListNode* target){ if (mNodes.find(target->val) =..

https://leetcode.com/problems/lru-cache/description/ LRU Cache를 구현하라. LRU Cache 구현의 핵심은, list를 이용하여, 가장 최근에 사용한 데이터를 list의 제일 앞쪽에 위치시키고, 따라서 capacity가 꽉 차면 가장 마지막에 data를 삭제하는 것이다. 이때 데이터 접근에 따라 list에서 해당 데이터를 찾고 앞쪽에 위치시켜야 하는데, 이 검색시간을 O(1)로 하는게 문제 풀이의 핵심이라 할 수 있다.  결국 list의 iterator를 이용해 한번에 지워야 한다.  코드 더보기class LRUCache { int _capacity; list> _listData; // value, key. unor..

https://leetcode.com/problems/find-the-duplicate-number/description/ 아래와 같은 정수 배열이 주어질 때 단 하나의 중복 값이 존재한다. 이 값을 찾아라.  입력 배열을 수정하지 말고, 추가 메모리를 사용하지 말라. 이 문제가 linked list category인 이유가 있다. 따라서 해석이 중요한 문제다.  각 원소가 다음 원소의 index의 위치라고 한다면, 중복되는 값은 cycle의 시작 지점을 의미한다.  우선, cycle이 존재하는 지 판단하고, 그 지점을 찾는다.찾고 cycle의 시작점을 찾는다.  그러면 답이 찾아진다. 코드더보기int findDuplicate(vector& nums) { int idxFast = 0; int ..

https://leetcode.com/problems/linked-list-cycle/description/ 주어진 list에서 cycle이 있는지 판단하라. 검색법은 간단하다. fast와 slow pointer가 출발 이후 만난다면, cycle이 있다고 판단할 수 있다. code 더보기bool hasCycle(ListNode *head) { ListNode* slow = head; ListNode *fast = head; bool start = false; while (fast != nullptr && fast->next != nullptr) { // cout val next->val next->next; slow = slow->next; ..

Add Two Numbers - LeetCode 두개의 리스트가 주어질 때, 하나의 노드가 한 자리수의 숫자를 의미한다.더 리스트의 수를 더하라. carry에 주의해서 더하고 new list를 만든다. 코드 더보기ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* newHead = nullptr; ListNode* node = nullptr; ListNode* node1 = l1; ListNode* node2 = l2; ListNode* prev = nullptr; int carry = 0; while (node1 != nullptr || node2 != nullptr || carry > 0) { ..

Copy List with Random Pointer - LeetCode list가 주어지고 random 포인터가 랜덤하게 다른 노드를 가리키고 있을 때, 이 list을 deep copy 하라. 약간 난해한 문제. 우선 직관적으로 해 보면, 먼저 메모리를 할당해서 기본 list를 copy를 한다.다음으로 random 포인터의 위치를 index를 파악한다. 그리고 이 data를 이용해 새로 만든 리스트에서 random의 대상이 되는 노드를 찾아 연결한다.  시간 효율이 좋지 않을 것이 자명하다.  일단 코드 ..더보기Node* copyRandomList(Node* head) { Node* newHead = nullptr; Node* prev = nullptr; Node* node = hea..