[SEB FE] Section3 Daily Coding 09_rotatedArraySearch
문제
부분적으로 오름차순 정렬된 정수의 배열(rotated)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다.
부분적으로 정렬된 배열: 배열을 왼쪽 혹은 오른쪽으로 0칸 이상 순환 이동할 경우 완전히 정렬되는 배열
예시: [4, 5, 6, 0, 1, 2, 3]은 왼쪽으로 3칸 또는 오른쪽으로 4칸 순환 이동할 경우 완전히 정렬됩니다.
입력
인자 1 : rotated
number 타입을 요소로 갖는 배열
rotated[i]는 정수
인자 2 : target
number 타입의 정수
출력
number 타입을 리턴해야 합니다.
주의사항
rotated에 중복된 요소는 없습니다.
target이 없는 경우, -1을 리턴해야 합니다.
입출력 예시
let output = rotatedArraySearch([4, 5, 6, 0, 1, 2, 3], 2);
console.log(output); // --> 5
output = rotatedArraySearch([4, 5, 6, 0, 1, 2, 3], 100);
console.log(output); // --> -1Advanced
단순히 처음부터 끝까지 찾아보는 방법(O(N)) 대신 다른 방법(O(logN))을 탐구해 보세요.
힌트
이진 탐색(binary search)을 약간 변형하여 해결합니다.
문제 접근
우선, 이진 탐색은 정렬된 리스트에서 검색 범위를 줄여 나가면서 검색 값을 찾는 알고리즘이다. 이진 탐색 알고리즘을 수도코드로 표현하면 다음과 같다.
1. 배열의 중간 값을 가져와서
2. 검색 값과 비교한다
2-1. 중간값 === 검색값 - 탐색 종료
2-2. 중간 값 < 검색 값 - 중간값의 오른쪽 구간을 대상으로 탐색
2-3. 중간 값 > 검색 값 - 중간값의 왼쪽 구간을 대상으로 탐색
3. 검색값을 찾거나, 검색구간이 비어있을 경우 탐색 종료
코드로 구현할 경우에는 인덱스를 이용해서 최소, 최대값을 따로 저장해서 반복문을 통해서 이 값을 갱신해서 탐색하는 배열의 범위를 줄여나간다.
function binary(arr, target) {
let left = 0;
let right = arr.length-1;
while(left<=right){
let mid = parseInt((left+right)/2)
if(arr[mid]===target) {
return mid
} else if(target < arr[mid]) {
right = mid -1;
} else {
left = mid +1;
}
}
return -1
}solution
그런데 이 문제의 경우에는 입력되는 배열이 두 부분으로 나뉘어서 각각 정렬되어 있기 때문에 정렬된 두 부분의 경계를 고려해서 left와 right를 설정하는데 추가적인 로직이 필요하다.
const rotatedArraySearch = function (rotated, target) {
// O(n) solution:
//return rotated.findIndex((el)=> el === target)
//O(log n) solution:
let left = 0;
let right = rotated.length-1;
while(left<=right){
let mid = parseInt((left+right)/2)
if(rotated[mid]===target)return mid
// 왼쪽 절반이 정렬되어 있는 상태
if(rotated[mid]<rotated[left]){
if(target<=rotated[right] && target>rotated[mid]){
left = mid+1;
}else {
right = mid-1;
}
}
// 오른쪽 절반이 정렬되어 있는 상태
else{
if(target>=rotated[left] && target<rotated[mid]){
right = mid-1;
}else{
left = mid+1;
}
}
}return -1
};참고
