고정점 찾기

📌문제

고정점이란 수열의 원소 중 그 값이 인덱스와 동일한 원소를 의미한다. 

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

단 시간복잡도 O(logN)으로 알고리즘을 설계하시오.

 

📌풀이

O(logN)으로 고정점을 찾으려면 선형 탐색으로는 시간 제한에 맞게 문제를 해결할 수 없음

이진 탐색을 수행해서 빠르게 고정점을 찾아야 함

찾고자하는 값이 중간점과 동일하다고 가정하고 탐색 수행

중간점이 가리키는 위치의 값보다 중간점이 작은 경우, 왼쪽 부분을 탐색

중간점이 가리키는 위치의 값보다 중간점이 큰 경우, 오른쪽 부분을 탐색

 

📌코드

def binary_search(array, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    # 고정점을 찾은 경우 인덱스 반환
    if array[mid] == mid:
        return mid
    # 중간점이 가리키는 위치의 값보다 중간점이 작은 경우 왼쪽 확인
    elif array[mid] > mid:
        return binary_search(array, start, mid - 1)
    # 중간점이 가리키는 위치의 값보다 중간점이 큰 경우 오른쪽 확인
    else:
        return binary_search(array, mid + 1, end)


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

index = binary_search(array, 0, n - 1)

if index == None:
    print(-1)
else:
    print(index)

 

📌참고

https://g.co/kgs/eyd5SSd

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