궁금한게 많은 개발자 노트

해당 문제는 LRU Cache의 put/get동작을 직접 구현하는 문제로 LRU란 Least Recently Used원칙으로 cache를 유지하는 규칙을 뜻합니다. 즉 cache의 capacity가 가득 찼을 때 put일 들어오면, 가장 최근에 접근하지 않은 content를 삭제하고, 최근에 접근한 것들의 우선순위를 높이는 방식입니다. (새로 추가되면 가장 우선순위가 높음) Linked List와 hash table을 활용하여 구현하였습니다. Linked List의 head, tail을 사용하여 가장 최근에 사용한 content를 head에 두고, 우선순위가 가장 낮은 것은 tail에 있습니다. double linked list로 구현하여 hash table에 (key, node)로 저장해두어 key로 ..

해당 문제는 숫자로 이루어진 배열에서, 순서와 상관없이 배열 내 숫자 중 연속되어 증가하는 숫자들이 존재하는 것들 중 가장 긴 길이를 반환하는 문제입니다. 예를 들면 [100, 4, 200, 1, 3, 2]의 배열에서는 1,2,3,4가 연속하며 증가하는 가장 긴 숫자들이므로 4가 정답입니다. 이 문제를 해결하기 위해서는 우선 배열을 오름차순으로 정렬하고 나서 보면 연속되는 부분 배열들을 살펴보면 1,2,3,4와 100 그리고 200 이렇게 세 부분 배열로 나눌 수 있습니다. 이 경우에 각 시작점의 특징은 해당 숫자보다 -1인 숫자가 배열 내에 존재하지 않는다는 특징이 있습니다. 그래서 -1인 숫자가 배열에 존재하지 않으면 시작점으로 판단하고 하나씩 증가시키며 배열에 존재할 때까지의 길이를 비교하며 제일 ..

해당 문제는 두 Linked List가 주어지고, 각 링크드 리스트의 노드는 숫자를 나타내고 있으며 각 숫자는 head 부터 tail까지 한 숫자의 각 자릿수를 나타냅니다. 두 링크드 리스트의 숫자를 더한 결과의 링크드 리스트를 반환하는 문제입니다. 일반적으로 두 수의 덧셈은 가장 아랫자리부터 덧셈이 이루어지므로 stack에 각 링크드 리스트의 숫자를 넣어 가장 아랫자리부터 나올 수 있도록 준비하고 덧셈의 결과 값도 마찬가지로 stack에 넣어 링크드 리스트로 하나씩 빼내며 만들 수 있습니다. /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(n..

해당 문제는 숫자로 이루어진 배열에서, 서로 다른 인덱스 i, j, k가 i < j < k관계를 이루고, index에 존재하는 값도 nums[i] < nums[j] < nums[k]를 이루는 i, j, k가 존재하는지 여부를 판단하는 문제입니다. 연속성을 가질 필요는 없지만 해당 조건을 만족하기 위해서는 두 변수가 필요하고, 한 변수에는 가장 작은 값을 업데이트하고, 두 번째 변수에는 첫 변수보다 높은 값이 나타나면 업데이트, 그리고 세번째 아이템을 만났을 때 두번 째 변수보다 크다면 해당 조건을 만족하는 i, j, k가 존재한다는 의미입니다. 첫번째 변수가 채워졌는데 배열에서 다음 값이 더 작다면 다시 첫변수를 업데이트해주고, 더 크다면 두번째를 채우고, 두번째보다 더 큰 값이 나오면 조건을 만족한다고..

해당 문제는 숫자 배열과 diff가 주어졌을 때, arr의 subsequence 중에서 diff간격으로 이어지는 가장 긴 subsequence 길이를 반환하는 문제입니다. subsequence는 연속되지 않아도 됩니다. 특정 숫자로 시작하는 subsequence길이를 저장하는 것이 주요하여 map자료 구조를 사용하여 특정 숫자로 끝나는 subsequence의 최대 길이를 저장해두었습니다. subsequence는 diff를 더해가며 나오는 배열의 길이를 찾는 것이므로, i번째 숫자 - diff가 이미 map에 존재한다면 그 길이에 +1을 해서 i번째 숫자를 map에 저장해두고 반복해나가면 됩니다. 즉, arr[i] - diff가 map에 이미 존재한다면 arr[i] - diff까지의 길이 + 1을 arr[..