rotatedArraySearch 문제 뜯어보기
🔍 문제보기
문제:
부분적으로 오름차순 정렬*된 정수의 배열(rotated)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다.
- 부분적으로 정렬된 배열: 배열을 왼쪽 혹은 오른쪽으로 0칸 이상 순환 이동할 경우 완전히 정렬되는 배열
- 예시: [4, 5, 6, 0, 1, 2, 3]은 왼쪽으로 3칸 또는 오른쪽으로 4칸 순환 이동할 경우 완전히 정렬됩니다.
입력:
| 인자1 : rotated | 인자1 : target |
|
|
출력:
- 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); // --> -1
Advanced:
- 단순히 처음부터 끝까지 찾아보는 방법(O(N)) 대신 다른 방법(O(logN))을 탐구해 보세요.
힌트:
- 이진 탐색(binary search)을 약간 변형하여 해결합니다.
📝 이 문제는...
이진탐색(binary search)에 대해 알고 풀어야 시간복잡도가 O(logN)이 되어 통과하는 문제이다.
💡 잠깐! 아이디어 생각해보기
1. 이진탐색(binary search)
이진 탐색에 대한 글은 링크의 글을 참고하여 정리하였다.
이진탐색을 쉽게 생각하면 숫자 맞추기 업다운 게임을 생각하면 된다.
간단하게 설명하자면 1~100까지의 숫자 중에 내가 생각하는 숫자 하나를 맞춰봐! 한다면
50으로 중간 숫자를 부른뒤 업다운을 듣고!
업이라면 또 50~100의 반인 75를 불러서 추측을 듣는게 가장 안전할 것이다.
이런 원리를 사용하는 것이 이진 탐색이다.
일단 이진 탐색은 보통 왼쪽 영역을 의미하는 L과 오른쪽 영역을 의미하는 R이라는 변수를 할당해서 구현한다.
l(left)이나 r(right)대신에 low와 high 로 변수를 지정하는 경우도 있다. 본인 편한대로 하면 된다.
가운데 mid 인덱스를 계산해서 mid와 타겟을 비교해서 L와 R을 다시 한정지어주는 식으로 구현한다.
아래는 기본적인 이진탐색의 기본적인 코드이다.
const BinarySearch = (target, dataArray) => {
let l = 0;
let r = dataArray.length - 1;
let mid = Math.floor((l + r) / 2);
while(target !== dataArray[mid]){
if(target < dataArray[mid]){ //🌟만약 타겟이 중간 인덱스 값보다 작아 왼쪽에 있다면
r = mid - 1; //오른쪽을 끝을 중간인덱스 하나 전으로 옮겨온다.
mid = Math.floor((l + r) / 2); //중간인덱스도 재조정
}else{ //🌟만약 타겟이 중간 인덱스 값보다 커서 오른쪽에 있다면
l = mid + 1; //왼쪽 끝을 중간인덱스 하나 후로 옮겨온다.
mid = Math.floor((l + r) / 2); //중간인덱스도 재조정
}
//변경된 r또는 l과 mid값을 들고 다시 다음턴 while을 돈다.
}
return dataArray[mid] //target === dataArray[mid] 가 되면 while이 종료되고 리턴
}
2. 부분적으로 오름차순 정렬된 정수의 배열
전체가 오름차순이면 오름차순이지, 왜 부분만 또 오름차순이어서 문제를 복잡하게 낼까 싶었는데
이진 탐색의 성격을 정확하게 이해하고 문제를 효율적으로 푸는 방법을 알아야만 풀 수 있기 때문이 아닐까 싶다.
간단히 생각하면 부분 정렬을 sort를 써서 전체정렬을 시켜버리겠지만, 그런 작업 필요없이도
이진 탐색 하나만으로 더 효율적으로 풀 수 있다.
부분 정렬된 배열의 아래 성질들을 잘 이해할 수 있어야 한다.
- 왼쪽 절반과 오른쪽 절반, 적어도 둘 중 하나는 정렬되어 있다.
- 정렬된 부분의 처음과 끝 숫자를 타깃과 비교하면 정렬된 범위내에 숫자가 들어있는지 알 수 있다.
- 정렬된 절반의 처음과 끝 사이에 타깃이 없다면 정렬되지 않은 쪽에서 다시 절반을 나누어본다. 그러면 또 그 절반에서도 정렬된 쪽과 정렬되지 않은 쪽이 생긴다.
- 이렇게 범위를 좁혀가며 반복해서 찾다보면 타켓이 가운데 지점에서 걸린다.
🌟 문제풀이
const rotatedArraySearch = function (rotated, target) {
let left = 0, //⚓︎ anchor 박기
right = rotated.length - 1; //⚓︎ anchor 박기
while (left <= right) {
let middle = parseInt((right + left) / 2); //⚓︎ anchor 박기
if (rotated[middle] === target) { //🗂filter01:가운데에 target이 있는 경우 바로 리턴
return middle; //바로 찾았네!
}
if (rotated[left] < rotated[middle]) { //🗂filter02:어느쪽 절반이 정렬되어 있나?
// 왼쪽 절반이 정렬되어 있는 상태
if (target < rotated[middle] && rotated[left] <= target) { //🗂filter03:정렬되어 있는 범위에 target이 있을까?
right = middle - 1; //⚓︎ 범위좁혀서 anchor 박기
} else { //🗂filter03:정렬되어 있는 범위에 target이 있을까?
left = middle + 1; //⚓︎ 범위좁혀서 anchor 박기
}
} else { //🗂filter02:어느쪽 절반이 정렬되어 있나?
// 오른쪽 절반이 정렬되어 있는 상태
if (target <= rotated[right] && rotated[middle] < target) { //🗂filter03:정렬되어 있는 범위에 target이 있을까?
left = middle + 1; //⚓︎ 범위좁혀서 anchor 박기
} else { //🗂filter03:정렬되어 있는 범위에 target이 있을까?
right = middle - 1; //⚓︎ 범위좁혀서 anchor 박기
}
}
}
return -1; //이거 다해도 아무것도 리턴 안되면 없는 거니까 -1리턴
};
포인트는!
정렬되어 있는 범위에선 (일일히 비교하지 않더라도),
처음과 끝만 비교하여 해당 범위에 target이 존재하는지 알수 있고,
존재하더라도 ,혹은 존재하지 않더라도, 절반으로 범위를 좁힐 수 있다는 점이다.
위의 해답코드의 원리를 기본적으로 설명하는 그림을 만들어보았다.
예시는 배열이 짧아서 while문이 2번 도는 동안 끝나버렸지만,
길다면 당연히 더 많이 돌수도 있을 것이다. (반으로 좁혀나가고 비교하는 과정이 많아지게되니까)
하지만 입력갑과 정비례하여 O(n)으로 돌진 않을 것이다.
효율적인 알고리즘을 구현해 놓았기 때문에 입력값이 길어져도 길어진 것에 비해서 연산이 많이 늘어나진 않을 것이다.(O(logN))
