알고리즘 문제408 [Leetcode] 1217. Minimum Cost to Move Chips to The Same Position 문제 : https://leetcode.com/problems/minimum-cost-to-move-chips-to-the-same-position/ n의 크기인 position 1차원 배열이 있다. position[i]는 i 번째 칩의 위치를 의미한다. 한 번에 i 번째 칩의 위치를 왼쪽이나 오른쪽으로 두 칸 움직이는 비용은 0이고, 한 칸 움직일 때는 1의 비용이 든다. 모든 칩을 동일한 위치로 옮기려고 할 때 필요한 최소 비용을 구하라. 2만큼 움직이는건 비용이 들지 않으므로 짝수번 움직이는건 비용이 들지 않는 것과 같다. 따라서 0 비용으로 짝수번째 위치에 있는 칩들은 2번으로, 홀수번째 위치에 있는 칩들은 1번으로 먼저 옮긴다. 그리고 짝수, 홀수에 있는 칩들 개수 중 더 작은 개수의 칩들을 반.. 2021. 12. 7. [Leetcode] 337. House Robber III 문제 : https://leetcode.com/problems/house-robber-iii/ 이진 트리로 구성된 집들의 구조가 있다. 도둑은 집들에 침입해 도둑질을 하려고 하는데 연결된 집을 동시에 털면 경찰에 연락이 간다. 경찰에 연락이 가지 않게 집들을 도둑질하려고 할 때, 훔칠수 있는 최대 금액을 구해라. memoization을 위해 TreeNode*을 키 값으로 하고 해당 노드를 헤드노드로 한 서브트리에서 조건을 만족하며 훔칠 수 있는 최대 금액을 저장한다. 탐색 중인 노드를 훔쳤다면 왼쪽, 오른쪽 자식 노드들은 훔치면 안되므로 왼쪽 자식 노드의 자식 노드들, 오른쪽 자식 노드의 자식 노드들을 다시 헤드 트리로 하여 훔칠 수 있는 최대 금액들의 합이 정답이 될 수 있다. 또한 탐색 중인 노드를 .. 2021. 12. 5. [Leetcode] 1032. Stream of Characters 문제 : https://leetcode.com/problems/stream-of-characters/ 문자열 리스트 words가 입력으로 주어지고 추가될 알파벳 소문자가 한 글자씩 입력으로 들어온다. 추가될 알파벳들은 초기 빈문자열에서 뒤에 하나씩 추가된다. 알파벳이 하나씩 추가되어 만들어진 문자열의 접미사가 words 배열에 존재하는지 판단해라. 트라이(Trie)를 만들어야 한다. words 문자열들을 뒤에서 부터 탐색하면서 트라이를 만들어간다. 예를 들어, words = ["abc", "bc", "dc"] 인 경우 [그림 1]과 같은 트라이가 만들어진다. 1번 노드가 트라이의 헤드 노드이며 빨간색 체크한 부분이 문자열의 끝을 의미한다. 알파벳들을 하나씩 받으며 만들어진 문자열을 마찬가지로 뒤에서부터 .. 2021. 12. 4. [Leetcode] 82. Remove Duplicates from Sorted List II 문제 : https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ 정렬된 linked list의 head 노드가 주어지면 중복된 번호를 가진 노드들은 모두 삭제하고 고유한 번호를 가진 노드들만 남겨라. head 노드의 앞에서부터 탐색하며 탐색중인 노드의 next 노드가 없거나 탐색중인 노드의 val 와 next 노드의 val이 다른경우 고유한 노드가 된다. 이 경우 탐색중인 노드는 삭제하지 않고 남겨야 하므로 별도의 ListNode 포인터 변수(let, prev)에 저장해둔다. prev->next에 현재 노드를 연결시켜준 뒤 prev도 탐색중인 노드로 갱신한다. 그리고 최초로 찾은 고유한 노드는 새로운 head 노드가 되므로 이를 또 다른.. 2021. 12. 3. [Leetcode] 61. Rotate List 문제 : https://leetcode.com/problems/rotate-list/ linked-list 의 head 노드가 주어지면 오른쪽으로 k만큼 회전한 뒤의 linked-list의 head를 반환하라. 입력으로 주어진 링크드 리스트를 한 번 탐색하면서 전체 길이를 구한다. (let, cnt) 만약 오른쪽으로 cnt번 회전하면 원래의 링크드 리스트와 동일해지므로, 나머지 연산을 한 k % cnt 만큼만 오른쪽 회전시키면 된다. 링크드 리스트를 다시 한 번 탐색하면서 o -> o -> o -> o -> o 만일 위와 같은 링크드 리스트가 있고 k가 2라면 빨간색 노드가 새로운 헤드 노드가 될 것이다. 즉, head노드의 cnt - k번째 next 노드가 헤드노드가 된다. 회전한 뒤의 모습은 원래 링.. 2021. 12. 2. [Leetcode] 1526. Minimum Number of Increments on Subarrays to Form a Target Array 문제 : https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/ 양의 정수 배열 target과 동일한 크기의 초기값이 모두 0인 initial 배열이 있다. 한 번의 연산에서 initial 배열의 하위배열의 요소값들을 1씩 증가시킬 때, initial 배열에서 target 배열로 만들 수 있는 최소 연산 횟수를 구하라. 결국은 어느 부분을 하위 배열로 묶을 것인지를 찾는게 중요하다. target 배열을 앞에서부터 탐색하면서 이전 값 보다 탐색 중인 값이 더 큰 경우 이전 값과의 차이(하위 배열을 제외하고 추가로 증가되어야 하는 수)를 정답에 더해준다. 탐색하는 값이 이전 값보다 같거나 작다.. 2021. 11. 30. 이전 1 ··· 10 11 12 13 14 15 16 ··· 68 다음
