본문 바로가기

leetcode87

LeetCode 75 - Sort Colors (Medium) 문제 LeetCode - 75번 풀이 과정 0, 1, 2 로 구성되어 있는 배열을 O(n) 의 시간 복잡도와 O(1) 의 공간 복잡도를 통해 정렬하는 방법을 찾는 문제입니다. 처음에 어떻게 접근해야할지 감을 못잡아서 다른 사람의 풀이에 힌트를 얻어 해결할 수 있었습니다. 가장 중요한 것은 0 을 왼쪽에 2 를 오른쪽에 배치시켜야 한다는 것입니다. 따라서 배열을 순회하며 1 은 무시하고 0 과 2 를 만나면 들어갈 다음 위치를 가리키는 두 개의 포인터를 통해 위치를 변경해주면 O(n) 에 해결할 수 있습니다. 이때 주의할 점은 2 를 바꿀때인데 2를 swap 할 경우 0, 1, 2 중 하나의 숫자가 바뀐 위치로 오게 되는데, 여기서 walker 를 그대로 증기시켜버리면 경우에 따라서 정렬이 다 끝나지 않고.. 2021. 3. 4.
LeetCode 416 - Partition Equal Subset Sum (Medium) 문제 LeetCode - 416번 풀이 과정 주어진 배열에서 두 그룹으로 나누었을 때 두 그룹의 합이 같은 경우가 존재하는지 찾는 문제입니다. 0-1 knapsack 문제와 비슷하게 특정 인덱스의 숫자를 선택할지 안할지를 따져서 문제를 해결하면 됩니다. 우선 목표 합 target = total / 2 이며 나누어 떨어지지 않는 경우는 해가 존재하지 않으므로 이를 따로 예외처리합니다. 그 다음 dp[i, k] = i 이후 숫자들을 선택해서 합이 k 가 되는 경우가 존재하는지 라고 정의한다면 다음과 같은 점화식을 얻을 수 있습니다. dp[i, k] = dp[i+1, k-num[i]] or dp[i+1, k] 코드 /** * @param {number[]} nums * @return {boolean} */ v.. 2021. 3. 4.
LeetCode 560 - Subarray Sum Equals K (Medium) 문제 LeetCode - 560번 풀이 과정 특정 구간의 합이 k 이 되는 총 개수를 구하는 문제입니다. 원래 투 포인터 를 사용해서 구하려고 했는데 음수가 존재하기 때문에 올바른 값을 구할 수 없었습니다. 따라서 1차원 배열에 누적 합을 계속 기록하면서 계산을 수행합니다. 여기서 합이 k 가 되는 구간을 찾기 위해서는 다음과 같이 생각해볼 수 있습니다. a, b, ... e, f ... 만약 f 까지의 합이 30이고 우리가 찾는 k = 20 일 때 a ~ f 까지 숫자 중에서 합이 10 인 지점을 찾으면 됩니다. 그 이유는 a ~ b = 10 이라면 c ~ f 의 구간이 30 - 10 = 20 이 되기 때문입니다. (구간 합 알고리즘) 코드 /** * @param {number[]} nums * @pa.. 2021. 3. 4.
LeetCode 752 - Open the Lock (Medium) 문제 LeetCode - 752번 풀이 과정 문자열을 기준으로 특정 숫자에 도달하기 위한 최소 회전수를 구하는 문제입니다. 각 숫자에 대해서 증가하거나 감소할 수 있으며 deadends 에 포함되지 않는 숫자에 대해서만 탐색을 진행합니다. 따라서 조건에 맞도록 BFS 를 수행하며 목표 숫자에 도달하기 위한 최소 횟수를 구하면 됩니다. 코드 /** * @param {string[]} deadends * @param {string} target * @return {number} */ var openLock = function (deadends, target) { const digits = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]; function bfs(st.. 2021. 3. 4.
LeetCode 11 - Container With Most Water (Medium) 문제 LeetCode - 11번 풀이 과정 두 막대기를 기준으로 가장 많은 물을 담을 수 있는 방법을 찾는 문제입니다. 완전 탐색 으로 접근할 경우 O(N^2) 에 문제를 해결할 수 있지만 투 포인터 를 사용하면 O(N) 에 가능합니다. 두 막대가 다음과 같이 존재한다고 하겠습니다. 편의상 2, 1, 4 크기의 막대를 각각 다른 위치에 그렸지만 사실은 가장 왼쪽과 오른쪽 막대 중간의 어느 특정 위치 X 에 위치할 수 있는 막대의 3 종류를 나타낸 것입니다. 위와 같이 가장 왼쪽에 위치한 막대를 L 그 반대를 R 이라고 했을 때 어느 포인터를 옮겨야 최대 적재 컨테이너를 구할 수 있을까요? 만약 R 의 포인터를 왼쪽으로 옮길 경우 2, 1, 4 막대 모두 R 보다 작기 때문에 절대 더 큰 컨테이너를 구할 .. 2021. 3. 4.
LeetCode 763 - Partition Labels (Medium) 문제 LeetCode - 763번 풀이 과정 투 포인터 와 그리디 알고리즘 을 사용하는 문제입니다. partition 이 특정 문자들의 집합으로 이루어져 있을 때 가장 많은 partition 으로 나누기 위해서는 우선 다음과 같이 생각해볼 수 있습니다. 먼저 partition A 의 가장 첫 문자가 a 라고 한다면, 해당 partition 에는 문자열 S 에 존재하는 모든 a 를 포함해야합니다. 따라서 문자열 S 에서 가장 마지막에 존재하는 a 를 포함해야합니다. 그러므로 partition 의 기준이 되는 포인터 right 와 각 partition 의 문자들을 검사하기 위한 포인터 left 를 선언해서 탐색을 수행하면 됩니다. 코드 /** * @param {string} S * @return {numbe.. 2021. 3. 4.

티스토리툴바