📜 문제
- 정렬된 nums 배열이 있다.
- nums 배열은 1~n번 회전 한다.
1번 회전할 때마다 가장 뒤에있는 원소가 nums 배열의 맨 앞으로 온다.
k번 회전한 nums 배열이 주어질 때, 배열에서 가장 작은 값을 반환하는 문제이다.
(1<=k<=n)
시간복잡도가 O(logN)으로 제한돼 있으므로, 평균 O(NlogN) 이상인 sort 함수를 사용할 수 없다.
당연함 함수 쓰면 문제 푸는 의미가 없음
접근
- 극한의 효율을 추구하고 싶어서 nums 배열을 탐색하지 않아도 되는 경우는 바로 return 한다.
탐색하지 않아도 되는 경우: N번 회전해서 오름차순인 경우
1번 이라도 회전이 진행된 경우 배열에서 가장 큰 뒤의 원소가 맨 앞으로 온다.
그렇게 되면, 무조건 맨 앞 원소는 맨 뒤 원소보다 크기 때문에 정렬이 무너진다.따라서 nums가 오름차순으로 정렬된 경우는 n번의 회전이 이루어져서 원상태로 복귀된
nums[0] < nums[nums-length-1]인 경우다
- nums 배열을 대상으로 이진 탐색을 진행한다.
-
위 그림처럼 회전이 발생한 경우, nums가 완전 정렬이 아닌 부분정렬이 돼 있다.
따라서 가운데(half)를 중심으로 앞단 또는 뒷단에 위치하기 때문에 어느 한 쪽만 탐색할 수 없다. -
최솟값을 저장하는 전역 변수 min을 생성해, 이진 탐색을 진행하며 가장 작은 값을 저장한다.
-
탐색을 마친 경우, min을 반환한다.
가운데를 중점으로 앞/뒷단 모두 탐색한하는 게 포인트다.
✍ 부분 코드 설명
main 함수 & min 변수 작성
class Solution {
private static int min;
...
public int findMin(int[] nums) {
min = Integer.MAX_VALUE;
// the nums is sorted
if(nums[0]<nums[nums.length-1]){
return nums[0];
}
int res = binarySearch(nums,0,nums.length-1);
return res;
}
}- nums 배열이 모두 정렬된 경우면 맨 앞 원소가 최솟값이므로 nums[0]을 반환 및 종료한다.
- 그 외의 경우 binarySearch 함수를 호출해 탐색을 시작한다.
binarySearch 함수
public static int binarySearch(int [] nums, int start, int end){
if(start > end){
return min;
}
int half = (start+end)/2;
if(nums[half]<min){
min = nums[half];
}
binarySearch(nums,half+1,end);
binarySearch(nums,start,half-1);
return min;
}- start가 end 보다 큰 경우, 주어진 배열을 모두 탐색했으므로 현재 최솟값을 반환한다.
- 중간 인덱스인 half를 구하고, half가 현재 최솟값보다 작은 경우, 최솟값을 half로 갱신한다.
- half를 기준으로 앞단, 뒷단을 다시 탐색한다.
- 최솟값인 min을 반환하며 함수를 종료한다.
🍳 전체 소스 코드
class Solution {
private static int min;
public static int binarySearch(int [] nums, int start, int end){
if(start > end){
return min;
}
int half = (start+end)/2;
if(nums[half]<min){
min = nums[half];
}
binarySearch(nums,half+1,end);
binarySearch(nums,start,half-1);
return min;
}
public int findMin(int[] nums) {
min = Integer.MAX_VALUE;
// the nums is sorted
if(nums[0]<nums[nums.length-1]){
return nums[0];
}
int res = binarySearch(nums,0,nums.length-1);
return res;
}
}✨ 결과
이진 탐색을 재귀 또는 반복문으로 구현할 수 있는데 이 문제는 재귀로 구현해야 했다.
나는 재귀 종료 조건을 설정하는 게 어려워서 매번 고생을 좀 하는데, 이번엔 쉽게 떠올라서 기분이 좋았다 우히히
