회전된 점수판에서 최솟값이 처음 나타나는 위치
자바스크립트 코딩테스트 문제로 rotated-binary-search 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
한 번 회전된 오름차순 배열에서 가장 작은 값이 있는 위치를 찾는 문제입니다.
문제 설명
정수 배열 scores가 주어집니다.
이 배열은 서로 다른 정수로 이루어진 오름차순 배열을 어떤 지점에서 한 번 잘라 앞뒤를 바꿔 만든 결과입니다. 회전이 전혀 일어나지 않았을 수도 있습니다.
배열에서 가장 작은 값이 처음 나타나는 인덱스를 반환하는 findRotationMinIndex 함수를 작성하세요.
예를 들어 [40, 55, 70, 5, 10, 20, 30]은 원래 [5, 10, 20, 30, 40, 55, 70]이었고, 최솟값 5의 인덱스는 3입니다.
제한사항
scores의 길이는1이상100,000이하입니다.scores의 원소는-1,000,000,000이상1,000,000,000이하의 정수입니다.- 모든 원소는 서로 다릅니다.
- 입력은 오름차순 배열을 한 번 회전한 형태임이 보장됩니다.
- 가능한 한
O(log n)에 가깝게 해결해 보세요.
예시
- 입력:
scores = [40, 55, 70, 5, 10, 20, 30]→ 출력:3 - 입력:
scores = [3, 8, 12, 14, 19]→ 출력:0 - 입력:
scores = [15, 18, 2, 4, 7, 11]→ 출력:2
힌트
- 회전된 배열에서도 어느 한쪽 구간은 여전히 정렬된 상태입니다.
mid값과right값을 비교하면 최솟값이 왼쪽 절반에 있는지, 오른쪽 절반에 있는지 판단할 수 있습니다.- 완전히 정렬된 구간만 남았을 때의 맨 앞 원소가 그 구간의 최솟값입니다.
해설
이 문제는 선형 탐색으로도 풀 수 있지만, 배열이 원래 오름차순이었다가 한 번만 회전됐다는 성질을 이용하면 더 빠르게 찾을 수 있습니다.
핵심은 mid와 right를 비교하는 것입니다.
scores[mid] <= scores[right]라면mid부터right까지는 정렬되어 있으므로 최솟값은mid자신이거나 그보다 왼쪽에 있습니다.scores[mid] > scores[right]라면 정렬이 끊긴 지점, 즉 최솟값은mid의 오른쪽에 있습니다.
그래서 이분 탐색처럼 범위를 줄일 수 있습니다.
예를 들어 [40, 55, 70, 5, 10, 20, 30]을 보면:
mid = 3, 값은5,right = 6, 값은305 <= 30이므로 최솟값은 왼쪽 절반 포함 범위에 있습니다.- 범위를 계속 줄이면 결국 인덱스
3만 남고, 그 위치가 정답이 됩니다.
회전이 없는 [3, 8, 12, 14, 19] 같은 경우에도 같은 원리로 범위를 줄이면 최종적으로 인덱스 0이 남습니다.
이 방식은 탐색 범위를 절반씩 줄이므로 시간 복잡도는 O(log n)이고, 추가 공간은 O(1)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.