궁금한게 많은 개발자 노트

오름 차순으로 연결된 k개의 linked list를 하나의 오름 차순으로 연결된 linked list로 합쳐서 반환하는 문제입니다. min heap을 구현하여 node들을 heap에 모두 넣고, 하나씩 빼서 모두를 연결하여 반환하였습니다. queue library를 import하고, struct compare의 operator함수를 overriding하여 min heap을 선언하려 합니다. struct compare { bool operator()(const ListNode* a, const ListNode* b) { return a->val > b->val; } }; k개의 linked list를 모두 heap에 넣고, 하나씩 빼면서 prev node와 방금 뺀 node를 연결해주는 방식으로 구현하였습..

주어진 문자열 중에서 반복 되지 않는 문자로 구성된 sub string중 가장 긴 문자열을 찾는 문제입니다. map에 각 character별 index위치를 넣어두고, 같은 문자가 발견되면 이미 map에 index가 있다는 의미이므로 구간 길이를 조정해야 합니다. 현재 유효한 구간은 start - end이고 만약 map안의 index가 end보다 작은 경우는 의미가 없으므로, 현재 index가 아직 포함되지 않고 있더라도 end보다 작은 index이면 sub string길이를 비교하여 업데이트합니다. 만약, 그렇지 않고 유효한 길이 안에 같은 문자가 있다면 end 길이를 발견된 index + 1로 업데이트합니다. 매 문자마다 index를 업데이트해주어 linear time complexity에 해결할 수..

주어진 두 오름 차순으로 정렬된 linked list를 하나의 오름차순으로 정렬된 linked list로 합쳐서 반환하는 문제입니다. 기존 제공된 두 linked list의 node를 그대로 사용해야 하는 문제입니다. 해당 문제는 반복문으로도 해결할 수 있고, 같은 문제가 두 노드에 대해 반복되므로 재귀적으로도 해결할 수 있습니다. 먼저, 두 linked list의 노드 각각을 비교하여 a, b 리스트 중 b리스트의 현재 노드가 더 크다면 a 리스트에서 b 리스트 노드보다 더 큰 값이 나올 때 까지 노드를 지나가며 지나온 노드들을 b리스트 노드 앞에 배치시켜야 합니다. 반복문으로 해결한다면 다음과 같습니다. while (one != NULL && two != NULL) { if (one->val val)..

Binary Tree의 가장 깊은 depth의 크기를 반환하는 문제입니다. 재귀적으로 현재 노드 기준에서 왼쪽, 오른쪽 자식의 depth중 큰 값에 + 1하며 반환하면 root에서 가장 깊은 depth를 반환할 수 있습니다. /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *ri..

해당 문제는 Recursion을 사용하여 재귀적으로 같은 문제를 해결할 수 있는지를 판단하는 문제로 보였습니다. Linked List가 주어졌을 때, 서로 인접한 두개의 노드의 순서가 변경된 결과를 반환하는 문제입니다. ex) 1 -> 2 -> 3 -> 4 2 -> 1 -> 4 -> 3 작은 단위로 쪼개보면 인접한 두개의 노드가 서로 자리를 바꾸는 연산이 반복해서 일어나므로 재귀적으로 해결한다면 다음과 같은 코드로 풀이할 수 있습니다. 첫 번째 노드가 current, 두 번째 노드가 next라고 한다면 결과적으로 next->next는 current를 가리키고, current->next는 다음 두 노드의 변경된 첫 번째 노드를 가리켜야 합니다. 다음 두 노드의 결과는 swapPairs(next->next)..