문제 개요
오름차순으로 정렬된 배열이 있고, 이 배열이 사전에 알 수 없는 어떤 피벗(pivot)을 기준으로 회전되었다고 가정해 보겠습니다. 예를 들어, [0,1,2,4,5,6,7] 배열은 [4,5,6,7,0,1,2]처럼 변형될 수 있습니다. 검색할 target 값이 주어지며, 배열에서 해당 값을 찾으면 그 인덱스를 반환하고, 찾지 못하면 -1을 반환해야 합니다. 배열에는 중복 요소가 존재하지 않는다고 가정합니다.
예를 들어, 배열이 [4,5,6,7,8,0,1,2]이고 target이 0이라면, 0은 인덱스 5에 위치하므로 출력 결과는 5가 됩니다.
해결 접근 방법
이 문제는 변형된 이진 탐색(Binary Search)을 활용하면 O(log n)의 시간 복잡도로 해결할 수 있습니다. 일반적인 이진 탐색과 달리, 회전된 배열에서는 매 단계마다 어느 쪽 절반이 정렬되어 있는지 판단하고, 타겟이 해당 정렬 범위 안에 속하는지 확인하는 과정이 추가됩니다.
해결 단계는 다음과 같습니다.
- low := 0, high := 배열의 길이로 초기화합니다.
- low < high인 동안 아래 과정을 반복합니다.
- mid := low + (high - low) / 2 로 중간 인덱스를 계산합니다.
- arr[mid] == target이면 mid를 반환합니다.
- arr[low] <= arr[mid]라면 왼쪽 절반이 정렬된 상태입니다.
- target >= arr[low]이고 target < arr[mid]이면 high := mid로 설정하고, 그렇지 않으면 low := mid + 1로 설정합니다.
- 그렇지 않다면 오른쪽 절반이 정렬된 상태입니다.
- target <= arr[high - 1]이고 target > arr[mid]이면 low := mid + 1로 설정하고, 그렇지 않으면 high := mid로 설정합니다.
- 반복문이 종료되면 -1을 반환합니다.
Python 구현 예제
아래 코드를 통해 실제 구현을 살펴보겠습니다.
class Solution(object):
def search(self, nums, target):
low = 0
high = len(nums)
while low < high:
mid = low + (high - low) // 2
if nums[mid] == target:
return mid
if nums[low] <= nums[mid]:
if target >= nums[low] and target < nums[mid]:
high = mid
else:
low = mid + 1
else:
if target <= nums[high - 1] and target > nums[mid]:
low = mid + 1
else:
high = mid
return -1
ob1 = Solution()
print(ob1.search([4,5,6,7,8,0,1,2], 0))입력
[4,5,6,7,8,0,1,2]
0
출력
5
시간 및 공간 복잡도
- 시간 복잡도: O(log n) — 매 반복마다 탐색 범위가 절반으로 줄어듭니다.
- 공간 복잡도: O(1) — 별도의 자료구조 없이 포인터 변수만 사용합니다.
마무리
회전 정렬 배열에서의 검색은 코딩 인터뷰에서 자주 출제되는 대표적인 문제입니다. 핵심은 매 단계에서 어느 쪽 절반이 정렬되어 있는지 파악하고, 타겟이 해당 정렬 범위 안에 있는지 확인한 뒤 탐색 방향을 결정하는 것입니다. 이진 탐색의 원리를 잘 응용하면 선형 탐색(O(n))보다 훨씬 효율적으로 답을 찾을 수 있습니다.