https://leetcode.com/problems/search-in-rotated-sorted-array
평가
결과 : 2회 실패 후 성공
풀이시간 : 53분
두 번의 실패 모두 엣지 케이스를 잘 처리하지 못했다.
어떤 상황에서 예외가 나올지 생각은 했지만 처리 과정에서 실수를 했다.
엣지 케이스가 있다면 예시와 함께 종이에 적어가면서 어떻게 처리할지 생각해보자.
적어도 나한테 있어서 머리로 연산하는 건 실수가 많은 것 같다.
아이디어
Original 배열의 인덱스를 사용해 회전한 배열의 값을 찾는 법
[0,1,2,3,4,5,6,7] 이라는 Original 배열이 있습니다.
여기에서 회전이 일어나 [4,5,6,7,0,1,2] 라는 배열이 만들어졌습니다.
회전을 시켰다고 숫자들의 순서가 바뀌지는 않습니다.
1 -> 2 -> 3 -> ... -> 7 -> 1 이라는 값이 4 -> 5 -> ... -> 3 -> 4 로 바뀐 거 뿐이에요.
그렇다면 Original 배열의 인덱스를 회전한 배열의 인덱스로 변환할 수 있지 않을까요?
논리주소를 물리주소로 매핑하는 건데요. 예시를 보면 이해가 가실 겁니다.
- Original 배열의 0번 인덱스를 조회하면 -> 회전한 배열의 4번째 인덱스의 값을 반환하면 됩니다. (값은 0입니다)
- Original 배열의 1번 인덱스를 조회하면 -> 회전한 배열의 5번째 인덱스의 값을 반환하면 됩니다. (값은 1입니다)
- Original 배열의 6번 인덱스를 조회하면 -> 회전한 배열의 3
(6 + 4)%7번째 인덱스의 값을 반환하면 됩니다. (값은 7입니다)
공식으로 정리하면 물리주소 == (논리주소 + 회전이_일어나_움직인_길이) % 배열 크기 입니다.
이제 회전이 일어나서 각 배열들이 몇 칸씩 움직였는지만 계산하면 우리는 문제를 풀 수 있습니다.
몇 칸이 이동했는지 찾는 법
원래 Original 배열은 오름차순으로 정렬되어 있습니다. 따라서 회전한 배열에서 가장 작은 값을 찾습니다.
위 예시에서는 4번째 인덱스가 되겠네요.
0번째 인덱스가 N번째 인덱스에 있다는 말은 N칸을 이동했다는 의미입니다. 자세한 설명은 생략할게요!
배열의 어느 위치에 Original 배열의 0번 인덱스가 위치하는지를 찾으면 되는데... 글로 설명하면 어려우니 예시로 쉽게 설명하겠습니다.
회전한 배열 [4,5,6,7,0,1,2] 에서 4번째 인덱스가 원래 인덱스입니다.
어떻게 그걸 알 수 있나요?
배열은 원래 오름차순으로 정렬되어 있다고 했습니다.
4 -> 5 -> 6 -> 7 모두 오름차순 정렬이 잘 되어 있습니다.
하지만 7 -> 0은 오름차순 정렬이 되어 있지 않죠.
그 이유는 원래 배열에서 0이라는 값이 시작점이고, 7이라는 값이 끝점이기 때문입니다.
이어서 확인해보면 0 -> 1 -> 2 역시 오름차순을 만족합니다.
정리하면 회전한 배열에서는 딱 한 지점에서만 오름차순을 만족하지 않습니다.
그 상황을 살펴보면 Original 배열의 시작점이 어디에 있는지 알 수 있습니다.
만약에, 모든 위치에서 오름차순을 만족한다는 건 회전을 한 칸도 하지 않았다는 의미가 되겠죠?
자세한 설명은 역시 생략하겠습니다.
이제 수도코드를 통해 살펴보겠습니다.
수도코드
몇 칸을 이동했는지 찾는다(); // logN
// 이진탐색을 진행한다
while(l<h) {
int mid = (l + h) / 2;
// 논리주소 mid를 물리주소로 변환한다
int physicalMid = (mid + movingCnt) % nums.length;
if nums[physicalMid]가 찾으려는 값이면
return physicalMid;
if (찾으려는값 < nums[physicalMid]) {
h = physicalMid;
} else {
l = physicalMid + 1;
}
}
// 모든 위치를 탐색했는데 값이 없음 -> -1을 반환한다
return -1;// 엣지케이스: nums가 0, 1, 2일 때
def 몇 칸 이동했는지 찾기():
배열의 크기가 0,1,2일때는 엣지 케이스이다. 해당 상황들을 처리한다.
while(l<h):
int mid = (l + h) / 2;
// 엣지케이스입니다.
if mid == h-1:
mid - 1과 mid 번째 원소들을 비교합니다.
오름차순이 깨진다면 mid가 배열의 시작 위치입니다.
그렇지 않다면 해당 배열은 오름차순이 깨지지 않았다는 의미가 됩니다.
if 지금 위치가 오른쪽값보다 크면:
// ex. [2,3,4,1] 에서 내가 4일 때
// mid + 1이 원래 배열의 시작 위치입니다.
return mid + 1;
if 왼쪽값이 지금 내 값보다 크면:
// ex. [2,3,4,1] 에서 내가 1일 때
// 지금 위치가 원래 배열의 시작 위치입니다.
return mid;
// 오름차순 정렬이 깨졌습니다.
// 이 경우가 가능하다는 건 mid와 high 사이 어딘가에서 원래 배열의 시작점(가장 작은 값) 이 있다는 의미입니다.
// 그렇기 때문에 low를 이동시킵니다.
if (nums[mid] > nums[h - 1]):
l = mid + 1
// mid번째 값이 가장 마지막 값보다 작다는 건 mid와 high는 잘 정렬되어 있다는 의미가 됩니다.
// 배열의 시작점은 low와 mid 사이에 있기 때문에 high를 이동시킵니다.
else:
h = mid;정답 코드
class Solution {
public int search(int[] nums, int target) {
int movingCnt = findMovingCnt(nums);
// System.out.println(movingCnt);
int l = 0;
int h = nums.length;
while(l<h) {
int mid = (l+h)/2;
// 논리위치 l, m, h
// 실제위치는 movingCnt를 더해주고 nums.length로 나머지연산을 해야 함
int findValue = nums[(mid + movingCnt) % nums.length];
if (target == findValue) {
return (mid + movingCnt) % nums.length;
} else if (target > findValue) {
l = mid + 1;
} else if (target < findValue) {
h = mid;
}
}
// 답이 없는 경우
return -1;
}
public int findMovingCnt(int[] nums) {
int l = 0;
int h = nums.length;
if (nums.length == 1) {
return 0;
}
if (nums.length == 2) {
if (nums[0] < nums[1]) {
return 0;
}
return 1;
}
while(l < h) {
int mid = (l + h)/2;
// System.out.println(l + " " + h +" "+ mid);
if (mid == nums.length - 1) {
if (nums[mid - 1] >= nums[mid]) {
return mid;
}
break;
}
if (mid == 0) {
if (nums[mid] >= nums[mid + 1]) {
return mid + 1;
}
break;
}
if (nums[mid] >= nums[mid + 1]) {
return mid + 1;
}
if (nums[mid - 1] >= nums[mid]) {
return mid;
}
// 정렬된값에서는 있을 수 없는 경우 -> mid, h 사이에 어딘가에 시작점이 있음
if (nums[mid] > nums[h-1]) {
l = mid + 1;
} else {
h = mid;
}
}
return 0;
}
}