Chap 15. 이진탐색 - Q28. 고정점 찾기

@mildsalmon·2021-10-12 09:03

1. 고정점 찾기

난이도
- 중하
풀이 시간
- 20분
시간 제한
- 1초
메모리 제한
- 128 MB
출처
- Amazon 인터뷰

A. 📜 문제

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

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

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

a. 예를 들면.

고정점을 예를 들면 수열 a = {-15, -4, 2, 8, 13}이 있을 때 a[2] = 2이므로, 고정점은 2가 된다.

b. 입력 조건

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

c. 출력 조건

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

d. 테스트 케이스

입력 예시


5
-15 -6 -1 3 7


7
-15 -4 2 8 9 13 15


7
-15 -4 3 8 9 13 15

출력 예시
```
3
```
```
2
```
```
-1
```

B. 💡 내 답안

a. 😊 1차 시도 (성공)


def bi(start, end):
    if start <= end:
        mid = (end + start) // 2

        if mid == array[mid]:
            answer = mid
        elif mid > array[mid]:
            answer = bi(mid+1, end)
        elif mid < array[mid]:
            answer = bi(start, mid-1)
        return answer
    else:
        return -1

global array

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

start = 0
end = len(array)

array.sort()

answer = bi(start, end)

print(answer)

b. 😊 2차 시도 (성공)


n = int(input())  
array = list(map(int, input().split()))  
  
start = 0  
end = n  
answer = None  
  
while start <= end:  
    mid = (start + end) // 2  
  
 if mid == array[mid]:  
        answer = mid  
        break  
  
 if mid < array[mid]:  
        end = mid - 1  
 elif mid > array[mid]:  
        start = mid + 1  
  
if answer == None:  
    print(-1)  
else:  
    print(answer)