Search

고정점 찾기

문제 : 고정점 찾기

고정점이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미한다. 예를 들어 수열 a = [-15, -4, 2, 8, 13]이 있을 때, a[2] = 2이므로, 고정점은 2가 된다. 하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 원소가 오름차순으로 정렬되어 있다. 이 때 이 수열에서 고정점이 있다면, 고정점을 출력하는 프로그램을 작성해라. 고정점은 최대 1개만 존재한다. 만약 고정점이 없다면 -1을 출력한다. 단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받는다.

입력 조건

첫째 줄에 N이 입력된다.(1 <= N <= 1,000,000)
둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력된다.(−10⁹ ≤ 원소의 값 ≤ 10⁹)

출력 조건

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

입출력 예시

5 -15 -6 1 3 7
Python
7 -15 -4 2 8 9 13 15
Python
7 -15 -4 3 8 9 13 15
Python
3
Python
2
Python
-1
Python

풀이

해결에 필요한 핵심 아이디어: 이진(이분)탐색!

해결 시나리오

이진 탐색 알고리즘 구현
시작 인덱스와 끝 인덱스의 중간값으로 중간 인덱스 mid를 계산
mid > array[mid]
→ 현재 mid의 오른쪽 범위 탐색 필요
mid < array[mid]
→ 현재 mid의 왼쪽 범위 탐색 필요
풀이

나동빈님 컨텐츠를 이용하시면 더 많고 자세한 내용을 얻을 수 있습니다.