부분적으로 오름차순 정렬된 정수의 배열과 정수를 입력받아 정수의 인덱스를 리턴해야 합니다.
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); // --> -1
부분적으로 정렬된 배열 다시말해 쉽게 모두 정렬된 배열로 만들어 줄 수 있다.
let cnt = 0;
while(true){
if(rotated[0] > rotated[1]){
let num = rotated.shift()
rotated.push(num)
cnt++;
break;
}
let num = rotated.shift();
rotated.push(num)
cnt++;
}
다음 코드를 통해서 부분 정렬된 배열을 온전히 정렬된 배열로 만들어 줄 수 있다. 그리고 그 이동한 만큼의 인덱스도 cnt
에 기억시켜둘 수 있다. 이제 여기서 이전에 배운 binary search
를 실행하면 된다.
const rotatedArraySearch = function (rotated, target) {
// TODO : 여기에 코드를 작성합니다.
let cnt = 0;
while(true){
if(rotated[0] > rotated[1]){
let num = rotated.shift()
rotated.push(num)
cnt++;
break;
}
let num = rotated.shift();
rotated.push(num)
cnt++;
}
let start = 0;
let end = rotated.length - 1;
let mid;
while(start <= end){
mid = Math.floor((start + end) / 2)
if(rotated[mid] === target){
return (mid + cnt) % rotated.length;
}else if(rotated[mid] > target){
end = mid - 1;
}else{
start = mid + 1;
}
}
return -1;
};
위 코드를 실행하면 원하는 인덱스는 추출이 가능하지만 테스트는 통과하지 못한다. 아마 이것도 Advanced 레벨을 한번에 통과해야하는 모양이다.
아마 위의 코드는 시간 복잡도가 효율성이 많이 떨어지는 것 같다. 그도 그럴 것이 첫번째 while
문이 그냥 for
문을 쓰는 것만 못한 것 같다. 그렇다면 이걸 어떻게 해야할까 한번 더 고민해봤다.
const rotatedArraySearch = function (rotated, target) {
// TODO : 여기에 코드를 작성합니다.
let start = 0;
let end = rotated.length - 1;
let mid;
while(start <= end){
mid = Math.floor((start + end) / 2)
if(rotated[mid] === target){
return mid;
}
if(rotated[start] <= rotated[mid]){ //왼쪽 절반이 정렬되어 있으면
if(rotated[start] <= target && target <= rotated[mid]){
end = mid-1;
}else{
start = mid+1;
}
}else{ //오른쪽 절반이 정렬되어 있으면
if(rotated[mid] <= target && target <= rotated[end]){
start = mid+1;
}else{
end = mid-1;
}
}
}
return -1;
};
문제에 힌트가 있었다. binary search
를 조금만 변경해주면 됬다. 조금 더 세부적으러 나눠서 값을 찾아 들어가면 된다.
확실히 문제가 조금 복잡해지니깐 다른 삽질을 너무 많이 했다. 저 결론을 도달하기 까지 정말 많은 생각을해야했다. 솔직히 말하면 시간초과를 했다. 그럼에도 붙들고 생각해낸 결과이기에 만족은 하되 100% 만족스럽지는 못하다. 다른 공부할 시간을 잡아먹으면서 생각해낸 것이 아깝다...