문제 페이지
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
Find Minimum in Rotated Sorted Array II - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
나이브한 접근법
주어진 배열을 반복문으로 정직하게 트래버설 하여 O(n)만에 해답을 찾는다.
배열의 최대 길이가 5000이므로 아주 적절하다..
이진탐색 접근법
노테이션 및 분석
ㄱ. 원본 배열 A[0:n)은 오름차순 정렬되어 있다.
ㄴ. 입력으로 주어진 길이 n짜리 배열 nums[0: n)은, A[0: n)을 r=[1: n]번 우회전 한 버전이다.
ㄷ. nums[0] 를 r0라 하자.
ㄹ. nums에서 r0와 같은 원소 집합을 E / r0 보다 큰 원소들의 집합을 G / r0보타 큰 원소들의 집합을 L이라 하자.
ㄱ과 ㄹ에 의하여,
ㅁ. 배열 nums는 "E - G - L - E" 순서로 원소들이 구성되어 있다.
ㅁ에서 E 그룹이 앞쪽과 뒷쪽으로 나뉘어져 있으므로 문제를 추상화하기 어려움을 알게 될 것이다. (직접 ㅁ만으로 풀이를 시도해보라)
ㅂ. 따라서 앞쪽 E 그룹을 E0, 뒤쪽 E 그룹을 E1이라 하자.
ㅁ, ㅂ에 의해 다음과 같은 사실이 성립한다.
ㅅ. 배열 nums는 "E0 - G - L - E1" 순서로 원소들이 구성되어 있다.
ㅇ.한편 |G|, |L|, |E1| 모두 [0: n-1] 이다.
Q. 원소들을 그룹지어 뭉텅이로 바라보는 이유가 무엇인가?
A. 이진탐색을 적용하기 위해서이다.
binarySearch(A, target)의 정의는 i=[0: n)에서 target <= A[i] 인 i 중 가장 첫 번째를 찾으라는 것이다.
이진탐색의 정의에서 두 번째 인자가 predicate이 되도록 바꾼다면, 동일한 의미를 갖는 다른 표현을 찾을 수 있다.
binarySearch(A, greaterThanEqualToTarget)
두 시그니쳐 중에서 후자
predicate 기반의 시그니쳐로 이진탐색을 기억하는 것이 유용하다.
그룹 E, L, G는 값 r0를 기점으로 상호 배제적인 predicate을 만족하는 집단이므로 이진 탐색의 수혜를 누릴 것이다.
정답 찾기
정답의 후보
- G와 L의 경계지점
- 혹은 E0와 L의 경계지점
- 혹은 E
(각 분기가 언제 성립하는지 위쪽 그림을 참고하여 생각해보자.)
함수의 시그니쳐
함수를 작성하기 전에, 우리가 이 함수에게 요구하는 책임을 잘 식별하고 인자와 반환을 디자인하자.
int binSearch(int nums[], int s, int e, int r0)함수의 책임: 주어진 배열을 E, G, L 그룹으로 구분하여 효율적으로 이진 탐색하여 최솟값을 내 놓는다.
함수의 인자: 배열 / 탐색 범위 [s: e) / E, G, L 구분을 위한 기준값인 r0
구현하기
정해진 사실
잠깐 일반론을 꺼낸다.
알고리즘은 주어진 입력에서 "정해진 사실"을 파악하여 실행을 가속화한다. 이미 정해진 사실은 알고리즘이 직접 확인할 필요가 없기 때문이다.
Q. 우리가 도출한 ㅅ. ㅇ. 에 내포된 사실은 무엇인가?
A. 배열의 임의 원소가 L 그룹일 경우, 정답은 이 원소의 위치에서 반 시계방향 또는 equal인 위치에 존재한다는 사실.
A. 배열의 임의 원소가 G 그룹일 경우, 정답은 이 원소보다 시계방향인 위치에 존재한다는 사실.
그림을 참고하자.
(nums 배열을 순환 고리 형태로 그리겠다. 분석에 약간 편리함을 주지 문제 해결에 꼭 필요한 사항은 아니다.)
우리는 일반적인 이진탐색처럼, 주어진 배열의 중앙위치 mid를 검사할 것이다.
만약 이 녀석이 L그룹이면, 이 사실은 정답의 위치를 결정하므로, 다음 탐색 범위를 [start: mid)로 업데이트 할 수 있다.
G 그룹일 경우, 이 사실 역시 정답의 위치를 결정하므로, 다음 탐색 범위를 [mid+1: end) 범위로 업데이트 할 수 있다.
private int binSearch(int nums[], int s, int e, int r0) {
if (e - s < 1) {
// 아직 미작성
}
int mid = (s + e) / 2;
int value = nums[mid];
if (value < r0) { // at L
return binSearch(nums, s, mid, r0);
} else if (value > r0) { // at G
return binSearch(nums, mid + 1, e, r0);
} else { // at E
// 아직 미작성
}
}
정해지지 않은 사실
mid가 E 그룹일 경우는 어떨까? 이 사실이 imply하는 결정적인 하나의 사건이 있는가?
그렇지 않다. mid가 E 그룹이라면, 이 사실은 두 가지 사건을 내포한다.
1. mid가 E0 그룹인 경우: 다음 탐색 범위를 [mid+1: end)로 갱신하면 된다.
2. mid가 E1 그룹인 경우: 다음 탐색 범위를 [start: mid)로 갱신하면 된다.
두 사건을 묘사하는 그림을 살펴 보아라.
논 디터미니스틱 함이 문제이다.
"정해진 사실"이 없기 때문에 발생 가능한 모든 사건을
알고리즘이 직접 두 눈으로 확인해야하고, 수행한 실행 경로 중 찐 실행 경로를 하나 선정해야 한다.
(최종적으로 T(n) = 2*T(n/2) + O(C) = O(n) 알고리즘이 되어 큰 부담을 갖지는 않는다.
다시 일반론이다.
상호 배제적인 두 사건 A, B의 참과 거짓을 알고리즘이 확인하려고 한다. 어떻게 해야 할까?
확인 순서
우리가 멀티 스레드를 쓰진 않을 거기 때문에 프로그램의 실행 흐름은 시퀀셜하다.
즉, 두 사건을 확인하는 흐름도 시퀀셜하다: A - B 또는 B - A 순서로..
무엇이 맞는지 판단하기
A - B 순서로 확인한다고 치고, 각자 resultA와 resultB를 부수효과로 생산한다고 하자.
어느 사건이 맞는지 판단하는 로직은 두 가지 구성이 있다.
1. A, B 전부 수행한다음 resultA, resultB를 검사하는 방식.
2. A 수행 - resultA 확인 - B 수행 - resultB 확인 방식.
1, 2번 유일하게 써야하는 경우도, 뭘 써도 되는 경우도 있다.
1번 방식에서 result를 저장할 장소는 전역 변수 / 전역의 자료구조 / 호출자의 지역 변수 / 호출자의 지역 자료구조 등 적절히 선택하면 된다. 해시맵, 배열, 스택 등 개인 재량껏.
2번 방식을 사용하려면 스택을 몹시 추천한다.
함수의 호출의 동작을 생각해보자.
스택 프레임이 만들어져서 해당 함수 실행에 필요한 컨텍스트를 스택에서 관리하고, 호출이 끝나면 pop하여 모든 흔적을 지운다.
이런 컴퓨터의 행동을 똑같이 따라하자는 것이다.
사건 A가 양산하는 부수효과(상태 업데이트 등)를 스택이 받아먹도록 구현했다면
A가 거짓인 사건으로 뽀록나도! 그 부수효과가 스택 pop으로 말끔히 정리되기 때문에
이후 B의 사건의 수행에는 영향을 미치지 않는다.
우리는 아래 두 사건을 1 - 2 순서로 확인한 다음
1. mid가 E0 그룹인 경우
2. mid가 E1 그룹인 경우
1과 2의 실행 결과물을 스택 자료구조에 저장하겠다. 이 말은 재귀호출을 하겠다고 돌려 말한것이다.
- 함수를 호출하는 행위 자체가 각 사건을 위한 컨텍스트(스택)을 만들어 주는 것이고
- 호출의 결론이 각자의 스택에 적재되도록 하는 것이며
- 호출자의 지역변수로 그 결론값을 옮겨주는 행위이다.
마지막으로 어느 사건이 참인지 판단할 것이다.
1. 1번 사건이 참이면 Min(result1, result2) == result1이다.
2. 2번 사건이 참이면 Min(result1, result2) == result2이다.
3. result1 == result2일 경우 모든 predicate를 침해하지 않으니 괜찮다.
private int binSearch(int nums[], int s, int e, int r0) {
if (e - s < 1) {
// 미작성
}
int mid = (s + e) / 2;
int value = nums[mid];
if (value < r0) { // at L
return binSearch(nums, s, mid, r0);
} else if (value > r0) { // at G
return binSearch(nums, mid + 1, e, r0);
} else { // at E: non-deterministic
return Math.min(binSearch(nums, mid + 1, e, r0),
binSearch(nums, s, mid, r0));
}
}베이스 케이스
우리가 구현을 재귀 호출로 했기 때문에 base-case를 결정하자.
(end - start < 1)인 경우 공집합이 탐색 범위라는 소리다. 그러므로 이진 탐색을 관두고 start가 가리키는 원소를 반환하면 된다.
그런데 알고리즘 상 start 값이 nums.length 이상이 되는 경우가 있다. nums에 E와 G 그룹 밖에 없을 때
mid + 1 호출이 끝까지 일어나기 때문이다. 그러므로 이 경우를 상쇄하기 위해 % nums.length를 해준다.
/**
* @param nums the array
* @param s the s of search range [s: e)
* @param e the e of search range [s: e)
* @param r0 the element at nums[0]
* @return the minimum value in nums
*/
private int binSearch(int nums[], int s, int e, int r0) {
if (e - s < 1) {
return nums[s % N];
}
int mid = (s + e) / 2;
int value = nums[mid];
if (value < r0) { // at L
return binSearch(nums, s, mid, r0);
} else if (value > r0) { // at G
return binSearch(nums, mid + 1, e, r0);
} else { // at E: non-deterministic
return Math.min(binSearch(nums, mid + 1, e, r0),
binSearch(nums, s, mid, r0));
}
}엄밀하게 따지기
E 그룹이 정말로 논 디터미니스틱한 사건을 생성하는지 우리가 먼저 결정해 둔다면
알고리즘의 훨씬 더 줄여줄 수 있다.
- 만약 nums[e-1]이 r0와 같다면 E 그룹은 두 개의 논 디터미니스틱 사건을 생성한다.
- 그렇지 않으면, E 그룹은 정답의 위치를 결정한다.
이 사실에 동의하는가?
최종 제출
class Solution {
private int N = 0;
// Worst case: T(N) = 2*T(N/2) + C -> Θ(N)
// Best case: T(N) = T(N/2) + C -> Θ(logN)
public int findMin(int[] nums) {
N = nums.length;
return binSearch(nums, 0, nums.length, nums[0]);
}
/**
* @param nums the array
* @param s search range [s: e)
* @param e search range [s: e)
* @param r0 the first element of given rotated array
* @return the minimum value in nums[s: e)
*/
private int binSearch(int nums[], int s, int e, int r0) {
if (e - s < 1) {
return nums[s % N];
}
int mid = (s + e) / 2;
int value = nums[mid];
if (value < r0) { // at L
return binSearch(nums, s, mid, r0);
} else if (value > r0) { // at G
return binSearch(nums, mid + 1, e, r0);
} else { // at E: non-deterministic
if (r0 == nums[e - 1])
return Math.min(binSearch(nums, mid + 1, e, r0),
binSearch(nums, s, mid, r0));
else
return binSearch(nums, mid + 1, e, r0);
}
}
}재귀호출 쓰지 않기
아까 전에 그려놓은 E그룹의 두 케이스를 참조하라.
mid가 E 그룹이란 사실은, nums[e-1]에 L 그룹 혹은 E 그룹이 있다는 걸 내포한다.
따라서 다음 스캔 범위를 nums[s: e-1)로 업데이트 하는 방법을 적용해도 좋다.
이 접근법은 재귀호출을 쓰지 않고 구현할 수 있으며
최악의 경우 T(n) = T(n-1) + O(C) -> Theta(n)가 되므로 시간복잡도는 동일하다.