문제 정리

배열이 주어지고 배열 안에서 고정점을 찾아서 반환하라.

고정점은 인덱스와 값이 같은것을 말한다.

접근 방법

먼저 풀어보았던 방법은 bisect 모듈을 사용해서 이진 탐색을 해보았다.

고정점은 사실 주어진 배열의 길이 안에서만 존재할테니

배열의 범위 안에서 반복문을 수행하고 이진탐색으로 값을 찾는다.

찾은 index를 배열의 해당 index의 값과 비교하여 같을 경우 정답처리를 한다.

코드 진행

<aside> 🔥 사실 아래 방법은 해당 문제의 시간복잡도 O(logN)을 만족할것같지만,

괜찮은 코드는 아니라고 생각한다.

</aside>

1. 입력값 받기

   import bisect
   import sys
   
   def input():
       return sys.stdin.readline().strip()
   
   n = int(input())
   li = list(map(int,input().split()))
   

2. 이진탐색

   이진탐색으로 배열의 범위안에서 값이 배열에 존재하는지 찾는다.

   찾은 인덱스를 배열에 인덱싱하여 해당 값과 index가 같다면 정답처리를한다.

   for target in range(0, n):
       index = bisect.bisect_left(li, target)
       if index < n and li[index] == target and li[index] == index:
           print(index)
   

풀이 진행

<aside> 🔥 풀이는 bisect모듈을 사용하는것이아닌, bisect모듈의 원본을 참조해서 풀었다.

이해하기 쉽진 않았다.

</aside>

먼저 해당 아이디어는 아래 그림과 같다.

0부터 배열의 길이까지를 범위로 잡고

중간선을 설정해서 중간값과 중간인덱스를 비교한다.