[이코테] 고정점 찾기

출처 - 이것이 취업을 위한 코딩테스트다 with 파이썬

고정점 찾기

📌 문제

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

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

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

📋 코드

def binary_search(arr, start, end):
    if start > end:
        return -1

    mid = (start + end) // 2
    if mid > arr[mid]:
        return binary_search(arr, mid + 1, end)
    elif mid < arr[mid]:
        return binary_search(arr, start, mid - 1)
    else:
        return mid


N = int(input())
arr = list(map(int, input().split()))

start, end = 0, len(arr)-1
print(binary_search(arr, start, end))

💡 한마디

인덱스와 현재 값을 비교해서 구간을 좁혀가는 이진 탐색 알고리즘으로 풀었다.