LeetCode의 153번째 문제인 Find Minimum in Rotated Sorted Array를 함께 풀어보도록 하겠습니다.
문제
길이 n인 배열이 오름차순으로 정렬되어 있고 1부터 n 번 회전되어 있다고 가정해 보십시오.
예를 들어, 배열 nums = [0,1,2,4,5,6,7]는 다음과 같이 변할 수 있습니다:
- 4번 회전했을 때
[4,5,6,7,0,1,2] - 7번 회전했을 때
[0,1,2,4,5,6,7]
배열 [a[0], a[1], a[2], ..., a[n-1]]을 1번 회전하면 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]의 배열이 됩니다.
유일한 요소로 구성된 정렬된 배열 nums가 회전된 상태가 주어지면, 이 배열에서 가장 작은 요소를 반환하시오.
예제
입력: nums = [3,4,5,1,2]
출력: 1입력: nums = [4,5,6,7,0,1,2]
출력: 0입력: nums = [11,13,15,17]
출력: 11풀이 1
이 문제를 해결하는 가장 단순 무식한 방법은 정렬을 이용하는 것인데요. 주어진 배열을 오름차순 정렬하면 첫 번째 인덱스에 가장 작은 값이 위치할 것입니다.
파이썬으로 구현해볼까요?
class Solution:
def findMin(self, nums: List[int]) -> int:
nums.sort()
return nums[0]자바스크립트로도 짜보겠습니다.
function findMin(nums: number[]): number {
nums.sort((a, b) => a - b);
return nums[0];
}입력 배열의 길이를 n이라고 했을 때, 이 풀이의 시간 복잡도는 정렬로 인해서 O(n * log n)입니다.
별도의 메모리를 쓰는 부분은 없으므로 공간 복잡도는 O(1)이 되겠습니다.
풀이 2
우리는 최소값만 알면 되기 때문에 굳이 배열 전체를 정렬할 필요는 없을 것입니다. 첫 번째 원소의 값을 변수에 저장해놓고, 루프를 돌면서 두 번째 원소부터 마지막 원소까지 대소 비교를 하면서 최소값을 찾을 수 있습니다.
이 알고리즘을 파이썬으로 구현해볼까요?
class Solution:
def findMin(self, nums: List[int]) -> int:
min_num = nums[0]
for i in range(1, len(nums)):
min_num = min(nums[i], min_num)
return min_num같은 코드를 자바스크립트로 작성해볼께요.
function findMin(nums: number[]): number {
let min_num: number = nums[0];
for (let i = 1; i < nums.length; i++) {
min_num = Math.min(nums[i], min_num);
}
return min_num;
}정렬을 사용하지 않는 이 풀이의 시간 복잡도는 O(n)으로 개선이 됩니다.
풀이 3
정렬된 배열이 회전하면 값이 계속 커지다가 중간에 값이 확 작아지는 부분이 생기기 마련입니다.
두 번째 예제를 기준으로 생각을 해보면 4부터 7까지는 증가하다가, 0에서 감소하는 것을 볼 수 있습니다.
↗ ↗ ↗ ↘ ↗ ↗
4 5 6 7 0 1 2다시 말해서, 0 위치에서는 앞에 있는 값보다 현재 위치의 값이 더 작습니다.
nums[i - 1] > nums[i]반면에 0 위치를 제외한 곳에서는 모두 앞에 있는 값보다 현재 위치의 값이 더 큽니다.
nums[i - 1] < nums[i]그러므로 우리는 배열을 루프를 돌면서 앞의 값보다 현재 값이 더 작은 곳을 찾으면 되겠죠?
이 알고리즘을 파이썬으로 짜보겠습니다.
class Solution:
def findMin(self, nums: List[int]) -> int:
for i in range(1, len(nums)):
if nums[i - 1] > nums[i]:
return nums[i]
return nums[0]자바스크립트로도 구현해보았습니다.
function findMin(nums: number[]): number {
for (let i = 1; i < nums.length; i++) {
if (nums[i - 1] > nums[i]) return nums[i];
}
return nums[0];
}이 풀이도 입력 배열을 한 번 루프를 도므로 시간 복잡도가 O(n)입니다.
풀이 4
지금까지의 풀이에서는 입력 배열이 원래 정렬되어 있었다는 점을 전혀 활용하지 못했습니다. 이번에는 이분 탐색(Binary Search)을 사용하여 더 효율적으로 해결을 해보겠습니다.
배열을 절반으로 가르면 왼쪽 편이든 오른쪽 편이든 둘 중에 한 곳에는 회전하는 곳이 존재할텐데요. 이 곳에 가장 작은 값이 위치할 것입니다. 따라서 우리는 앞의 값보다 현재 값이 더 작은 곳을 발견할 때까지 이분 탐색을 진행하면 될 것입니다.
그런데 최소값이 배열의 좌측 절반에 있는지 우측 절반에 있는지는 어떻게 알아낼 수 있을까요?
배열의 중앙에 위치한 값을 배열의 첫 번째 값 비교하면 최소값이 왼쪽과 오른쪽 중 어느 쪽에 있는지 알아낼 수 있습니다.
mid를 배열에 중앙에 위치한 인덱스라고 했을 때, nums[0]이 nums[mid]보다 작으면, 좌측은 완전히 정렬이 되어 있다는 뜻이기 때문에, 반드시 우측에 최소값이 존재합니다.
만약에 왼쪽에 최소값이 있다면 nums[0]이 nums[mid]보다 작을 리가 없었을테니까요.
예를 들어, 아래와 같은 배열을 절반으로 가르면 우측에 최소값이 있습니다. 이 때 왼편을 보시면 값들이 정렬이 되어 있어 있는데, 우측은 정렬이 깨져있는 것을 볼 수 있습니다.
_______ | _________
4 5 6 7 8 9 0 1 2 3
👆
nums[0] = 4 < nums[mid] = 8이제 우측을 절반으로 자르면, 이번에는 왼편에 최소값이 있습니다. 이 때 오른편을 보시면 값들이 정렬이 되어 있어 있는데, 좌측은 정렬이 깨져있는 것을 볼 수 있습니다.
___ | ___
4 5 6 7 8 9 0 1 2 3
👆
nums[0] = 4 > nums[mid] = 1이제 좌측을 절반으로 자르면, 이번에는 우측에 최소값이 있습니다.
| _
4 5 6 7 8 9 0 1 2 3
👆
nums[0] = 4 < nums[mid] = 9이제 우측을 절반으로 자르면, 마침내 우리가 찾고자 하는 최소값을 만나게 됩니다.
|
4 5 6 7 8 9 0 1 2 3
👆그런데 입력 배열이 n번 회전하면, 원래의 완전히 정렬된 상태로 돌아오고, 최소값이 인덱스 0에 있기 때문에 구현할 때 주의가 필요한데요.
이 경우에는 배열을 아무리 절반으로 나누어도 앞에 있는 값보다 현재 위치의 값이 더 작은 경우가 나오지 않게 됩니다.
따라서 low 값을 0이 아닌 1로 초기화를 해주고, 최소값이 발견되지 않은 경우에는 배열의 첫 번째 값을 반환하도록 해줍니다.
그럼 이 부분에 주의해서 파이썬으로 구현해보겠습니다.
class Solution:
def findMin(self, nums: List[int]) -> int:
low, high = 1, len(nums) - 1
while low <= high:
mid = (low + high) // 2
if nums[mid - 1] > nums[mid]:
return nums[mid]
if nums[0] < nums[mid]:
low = mid + 1
else:
high = mid - 1
return nums[0]같은 코드를 자바스크립트로도 작성해보겠습니다.
function findMin(nums: number[]): number {
let low = 1, high = nums.length - 1;
while(low <= high) {
let mid = Math.floor((low + high) / 2);
if(nums[mid - 1] > nums[mid])
return nums[mid];
if(nums[0] < nums[mid])
low = mid + 1;
else
high = mid - 1;
}
return nums[0];
}이 풀이는 계속해서 검색 범위를 절반으로 줄여나가기 때문에 시간 복잡도가 O(log n)으로 향상이 됩니다.
마치면서
이 문제가 너무 어려우셨다면 비슷하지만 좀 더 쉬운 문제인 Binary Search도 풀어보시라고 추천드립니다. 이 문제가 너무 쉬우셨다면 비슷하지만 좀 더 어려운 문제인 Search in Rotated Sorted Array도 풀어보시라고 추천드립니다. 이분 탐색 알고리즘에 대해서는 별도 포스팅에서 자세히 다루었으니 참고해보시면 도움이 될 것 같습니다.