궁금한게 많은 개발자 노트

주어진 문자열 중에서 반복 되지 않는 문자로 구성된 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)..

두 string이 주어졌을 때, 서로 다른 두 위치의 값들을 한번만 바꿔 같은 string이 될 수 있으면 true를 return하고 그렇지 않으면 false를 return하는 문제입니다. 크게 두 가지 갈래로 나눌 수 있습니다. 두 string이 모두 같은 경우와 그렇지 않은 경우가 있습니다. 1. 두 string 같은 경우는 같은 문자가 포함되어 있지 않다면, 두 자리를 변경하면 같아질 수 없습니다. 같은 문자가 포함된 경우를 판단하는 것은 set을 사용하여 기존 문자열과 길이가 달라지는 것으로 판단 가능합니다. 2. 다른 경우는 two point로 양쪽에서 index를 출발하여 같은 자리를 비교하며 같지 않은 index를 각각 저장해두고 그 두 자리를 변경했을 때 같지 않다면 같은 문자열을 만들 수..