[Amazon 인터뷰] 고정점 찾기

문제 보기 ↓

 고정점이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미합니다. 예를 들어 수열 a = {-15, -4, 2, 8, 13}이 있을 때, a[2] = 2이므로, 고정점은 2가 됩니다.

 하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 원소가 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 고정점이 있다면, 고정점을 출력하는 프로그램을 작성하세요. 고정점은 최대 1개만 존재합니다. 만약 고정점이 없다면 -1을 출력합니다.

 단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘ㅇ르 설계하지 않으면 '시간 초과' 판정을 받습니다.

 

입력 조건

• 첫째 줄에 N이 입력됩니다. (1 <= N < 1,000,000)
• 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다.

출력 조건

• 고정점을 출력한다. 고정점이 없다면 -1을 출력합니다.

입력 예시1

5 
-15 -6 1 3 7

출력 예시1

3

입력 예시2

7 
-15 -4 2 8 9 13 15

출력 예시2

2

입력 예시3

7 
-15 -4 3 8 9 13 15

출력 예시3

-1

 

 아예 대놓고 이진탐색을 사용하라고 명시한 문제입니다. 리스트의 원소가 N개인 경우 완전(순차)탐색은 시간복잡도가 O(N)입니다. 반면 이진탐색의 경우 O(logN)입니다. 이진 탐색을 구현할 줄만 알면 쉽게 풀 수 있는 문제입니다. 아래는 소스코드입니다.

 

n = int(input())
array = list(map(int, input().split()))

start = 0
end = n - 1

# 정답을 -1으로 초기화
answer = -1

while start <= end:
    mid = (start + end) // 2
    
    if mid < array[mid]:
        end = mid - 1
        continue
    elif mid > array[mid]:
        start = mid + 1
        continue
    else:
        answer = mid
        break
            
print(answer)

 중요한 것은 아이디어입니다. 문제에서 주어진 제약조건은 두 가지입니다. 첫 번째는 N개의 원소가 모두 서로 다른 정수라는 것, 그리고 두 번째는 모든 원소가 오름차순으로 정렬되어 있다는 것입니다.

 

 우선 모든 원소가 오름차순으로 정렬되어 있다는 점은 이진탐색을 사용하라는 것을 다시 한번 명시해주는 것과 동일합니다. 중요한 것은 N개의 원소가 모두 서로 다른 정수라는 점입니다. 이 조건에 의해 인덱스와 인덱스에 해당하는 실제 원소를 비교하여 이진탐색의 방향성을 설정할 수 있습니다.

 

 만약 인덱스가 실제 값보다 작다면, 해당 인덱스보다 큰 경우는 고려할 필요가 없습니다. 인덱스는 공차가 1인 등차수열입니다. 반면 실제 값은 인덱스가 커질때마다 1 이상의 차이를 보이며 커집니다. 따라서 어떤 시점의 인덱스가 실제 값보다 작은 순간, 인덱스가 실제 값을 따라잡을 수 있는 방법은 없습니다. 반대의 경우도 물론 마찬가지입니다.

 

 위의 사항을 고려하여 이진 탐색을 수행하고, 인덱스와 실제 값이 같아지는 지점에서 answer 변수를 업데이트한 뒤 순회를 종료합니다. break되지 않는다면 정답은 -1이 됩니다.