궁금한게 많은 개발자 노트

0과 1로만 이루어진 배열에서 한 가지 원소를 제거하였을 때, 1로만 이루어진 가장 긴 subarry의 길이를 반환하는 문제. array를 순회하면서 나올 수 있는 경우의 수를 생각해보면 다음과 같습니다. [0] 1을 만난다면 현재 len을 증가시켜 줍니다. len++, zero_count = 0; [1] 0을 만나기 전 1이 없었다면 정답과 관련된 길이를 구할 수 없습니다. zero_coun++; [2] 0을 만나기 전 1이 있었고, 0을 만난게 처음이라면 정답과 관련된 길이를 해당 길이는 과거형이 됩니다. prev_len = len, len = 0; [3] 0을 두 번 만났다면 prev_len과 len모두 0이됩니다. 이렇게 해서 결국 prev_len + len의 길이가 가장 긴 경우가 정답이 됩니다..

오름 차순으로 연결된 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..