본문 바로가기

🏃 algorithm/leetcode93

LeetCode 108 - Convert Sorted Array to Binary Search Tree (Easy) 💡 문제 LeetCode - 108번 🎯 풀이 과정 구간 nums 에 대해서 이진탐색트리를 구성하기 위해 nums 의 중간값을 루트노드로하고 해당 노드를 제외한 나머지 두 구간에 대해 재귀적으로 트리를 구성하면 됩니다. 이 방식으로 문제를 해결할 수 있는 이유는 뭘까요? 구간 nums의 개수를 x 라고 하고 간단한 증명을 해보겠습니다. x 가 짝수(2n)이면 나머지 두 구간은 (n, n-1) 로 나뉘고, 홀수(2n-1)라면 (n-1, n-1) 로 나뉩니다. 때문에 두 트리간의 높이 차이가 1보다 큰 경우는 없게 됩니다. 👨‍💻 코드 /** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (va.. 2023. 6. 6.

LeetCode 328 - Odd Even Linked List (Medium) 💡 문제 LeetCode - 328번 🎯 풀이 과정 O(1) 의 공간 복잡도와 O(n) 의 시간 복잡도를 가지는 알고리즘을 이용해서 홀수번째와 짝수번째에 위치한 노드를 분리한 뒤에 두 리스트를 이어주는 작업을 해야합니다. 리스트의 첫번째 노드는 항상 홀수번째 노드이고 홀수와 짝수는 순서대로 나오는 것은 명백한 사실이니, 제약 조건을 만족하기 위해 한번의 리스트 탐색 도중에 prev 와 cur 포인터를 이용해서 이전 노드의 다음 노드 포인터가 현재 노드의 다음 노드를 가리키도록 변경합니다. 또한 두 리스트를 합치기 위한 mergePointer 도 가장 최신의 홀수번째 노드를 가리키도록 합니다. 모든 순회를 마치면 mergePointer 로 두 리스트를 이어주면됩니다. 이렇게 하면 입력받는 리스트와 별개로 .. 2023. 5. 29.

LeetCode 704 - Binary Search (Easy) 💡 문제 LeetCode - 704번 🎯 풀이 과정 정렬된 배열에서 특정 target 의 index 를 반환하는 문제입니다. 이분 탐색 을 이용하면 쉽게 해결할 수 있습니다. 👨‍💻 코드 /** * @param {number[]} nums * @param {number} target * @return {number} */ var search = function(nums, target) { let head = 0 let tail = nums.length - 1 let answer = -1 while (head target) { tail = mid - 1 } else { answer = mid break } } return answer }; 2023. 5. 14.

LeetCode 438 - Find All Anagrams in a String (Medium) 💡 문제 LeetCode - 438번 🎯 풀이 과정 문자열 s 에서 p 의 아나그램을 만족하는 모든 부분 문자열의 위치를 찾는 문제입니다. 문자열의 길이를 고려해서 최적의 시간 복잡도로 문제를 해결해야하는데, sliding window 를 활용하면 O(n) 에 모든 위치에서 아나그램을 판단할 수 있습니다. 먼저 p 를 구성하는 문자 빈도수 해시맵을 생성합니다. 이후 두 개의 포인터 left 와 right , 아나그램 구성에 필요한 문자 개수의 합을 위한 count 를 정의합니다. count 가 0이 되면 모든 문자들이 필요한 빈도수만큼 발견되었다는 것을 의미합니다. window 의 크기는 곧 p 의 길이와 같기 때문에 left 와 right 간의 간격이 window size 에 도달하면 left 를 하나.. 2023. 5. 14.

LeetCode 42 - Trapping Rain Water (Hard) 💡 문제 LeetCode - 42번 🎯 풀이 과정 웅덩이를 찾기 위해서는 단조감소 구간을 알아야합니다. O(n) 에 이를 알 수 있는 방법이 무엇일까요? 이를 위해 monotonic stack을 활용할 수 있습니다. height 의 인덱스를 i 라고 하겠습니다. (a) height[i] 가 stack top 보다 작다면 그냥 push 합니다. (b) stack top 값보다 크거나 같다면 push 하기전에 stack 에서 height[i] 보다 작거나 같은 값을 가지는 요소들을 모두 pop 합니다. 물 웅덩이의 크기를 알려면 높이 * 너비 를 알아야합니다. 너비는 index 값으로 쉽게 알 수 있고, 높이는 다음과 같이 구할 수 있습니다. min(height[stack[top-1]], height[i]).. 2023. 4. 30.

LeetCode 238 - Product of Array Except Self (Medium) 💡 문제 LeetCode - 238번 🎯 풀이 과정 배열 num 에서 i 번째 요소만 제외한 나머지 요소들의 곱을 i 번째 인덱스에 할당한 결과를 반환해야합니다. 이때 O(n) 의 시간복잡도로 수행되어야하고, 나누기 연산을 사용하면 안되는 제약조건이 있습니다. 이를 위해서 i 번째 요소를 제외한 나머지 요소들의 곱을 다음과 같이 나눠서 생각할 수 있습니다. answer[i] = num[0...i-1] * num[i+1...] 부분합 알고리즘을 차용하면, 위에서 필요한 구간곱을 미리 계산해놓을 수 있습니다. 한 배열에는 왼쪽에서부터 누적한 곱을 저장하고, 다른 배열에는 오른쪽에서부터 누적한 곱을 저장합니다. 그러면 위 식은 다음과 같이 바꿔서 계산할 수 있습니다. answer[i] = prefixLeft[.. 2023. 4. 24.

이전 1 2 3 4 ··· 16 다음

티스토리툴바