오랜만에 성가신 문제를 직면했다. 결국 자력으로 풀지 못하여 이렇게 포스팅으로 풀이를 남겨본다.
문제
부분적으로 오름차순 정렬된 정수의 배열(rotated)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 한다.
부분적으로 정렬된 배열: 배열을 왼쪽 혹은 오른쪽으로 0칸 이상 순환 이동할 경우 완전히 정렬되는 배열
예시: [4, 5, 6, 0, 1, 2, 3]은 왼쪽으로 3칸 또는 오른쪽으로 4칸 순환 이동할 경우 완전히 정렬된다.
힌트 : 이진탐색법을 변형하여 O(logN) 성능을 내는 알고리즘을 구현한다.
풀이
이진탐색법
이진탐색법은 사실 다음과 같이 구현된다.
- 배열이 오름차순으로 정렬되어있다.
- 배열의 중간값과 target 값을 비교한다.
- 찾는 target 값이 아닐 경우
3.1. target 값이 중간값보다 작을 경우 배열의 나머지 작은 값들만 비교한다.
3.2. target 값이 중간값보다 클 경우 배열의 나머지 큰 값들만 비교한다.- 2와 3을 반복하여 값을 찾아 해당 인덱스를 반환하고, 없으면 -1을 반환한다.
부분정렬배열 이진탐색법
하지만 현재 rotated된 배열은 3.1 가정에 해당되는 경우 나머지 큰 값들만 비교하려고 했을 때, 중간값의 인덱스보다 큰 인덱스를 가진 나머지 배열 요소가 큰 값이라는 보장이 없다. 반대 상황에서도 마찬가지다.
그래서 부분적으로 배열이 오름차순으로 정렬되어있다는 설정 하에 적어도 다음의 경우는 정렬을 보장한다.
- 중간값보다 배열의 맨 왼쪽에 있는 요소가 작은 경우, 중간값보다 작은 인덱스를 가진 요소들은 오름차순으로 정렬되어 있다는 것이 보장된다.
- 중간값보다 배열의 맨 오른쪽에 있는 요소가 클 경우, 중간값보다 큰 인덱스를 가진 요소들은 오름차순으로 정렬되어 있다는 것이 보장된다.
이제 target을 재탐색할 때 확인해야할 상황이 4가지가 구성된다.
- 중간값 왼쪽의 배열이 정렬되어 있다 보장되었을 때
1.1. target 값이 중간값보다 작고, target 값이 중간값 왼쪽 배열에 있다고 예측 -> 중간값 왼쪽 배열을 탐색
1.2. 그 외에는 중간값 오른쪽 배열에서 탐색을 해준다.- 중간값 오른쪽의 배열이 정렬되어 있다 보장되었을 때,
2.1 target 값이 중간값보다 크고, target 값이 중간값 오른쪽 배열에 있다고 예측 -> 중간값 오른쪽 배열을 탐색
2.2.그 외에는 중간값 왼쪽 배열에서 탐색을 해준다.
1.2와 2.2의 경우가 의아해진다. 해당 상황은 정렬의 보장이 안된 배열에서 target 값이 있을 여지를 확인해준다.
구현
const rotatedArraySearch = function (rotated, target) {
let start = 0;
let end = rotated.length - 1
const aux = (arr, target, start, end)=>{
if (start > end) return -1;
let pivot = Math.round((start + end) / 2);
if (arr[pivot] === target) return pivot;
if (arr[start] < arr[pivot]){
if(target < arr[pivot] && arr[start] <= target){
return aux(arr, target, start, pivot-1);
} else{
return aux(arr, target, pivot+1, end);
}
}else{
if(target <= arr[end] && arr[pivot] < target){
return aux(arr, target, pivot+1, end);
}
else{
return aux(arr, target, start, pivot -1);
}
}
}
return aux(rotated, target, start, end);
};
배운 점
[이전에 작성한 알고리즘]
const rotatedArraySearch = function (rotated, target) {
let start = 0;
let end = rotated.length - 1
const aux = (arr, target, start, end)=>{
if (start > end) return -1;
let pivot = Math.round((start + end) / 2);
if (arr[pivot] === target) return pivot;
let nextPivot;
let nextNum;
let right;
nextPivot = Math.round((pivot+1 + end)/2);
nextNum = arr[nextPivot];
if (arr[pivot] < target && nextNum < target) right = aux(arr, target, pivot+1, nextPivot -1);
else right = aux(arr, target, pivot+1, end);
let left;
nextPivot = Math.round((start + pivot -1) / 2);
nextNum = arr[nextPivot];
if (arr[pivot] > target && nextNum > target) left = aux(arr, target, nextPivot+1, pivot-1)
else left = aux(arr, target, start, pivot-1);
if(left === -1 && right === -1) return -1;
if(right > -1) return right;
if(left > -1) return left;
}
return aux(rotated, target, start, end);
};제 기능을 못하는 알고리즘을 처음 작성해봤다. 이유는 모든 경우를 다 탐색하지 못했기 때문이다. 좀 더 상황을 간단하게 정리하는 방법을 생각해야 할 것 같다.
이번 같은 경우는 정렬이 되어 있는 부분과 되어있지 않은 부분을 알고리즘으로 간단하게 구현하는 방법을 생각해내지 못해서 문제를 못 풀었던 것 같다.
