[Amazon 인터뷰] 고정점 찾기

[Amazon 인터뷰] 고정점 찾기

이진 탐색

 

 

 

[문제]

 

선형탐색이 아닌 이진탐색으로 푸는 문제

문제가 이미 오름차순으로 정렬되어 있기에 그대로 탐색을 진행하면 됨.

고정점은 최대 1개만 존재함을 체크 -> 발견 즉시 반복문을 나오게 됨

 

 

 

 

[과정]

• 시작점과 끝점을 저장
• 반복문 실행
  • 시작점의 값과 해당 인덱스의 데이터 값이 같은지 확인
    • 같다면 break
  • 끝점의 값과 해당 인덱스의 데이터 값이 같은지 확인
    • 같다면 break
• 결과출력

 

 

 

 

[소스코드]

 

# 고정점 찾기 2022-06-13

from bisect import bisect_left, bisect_right

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

result = ''
for i in range(n):
    start = i
    end = n-i-1
    
    if start == data[start]:
        result = data[start]
        break
    elif end == data[end]:
        result = data[end]
        break
    
if result == '':
    print('-1')
else:
    print(result)

 

 

---

 

 

[통과]

 

# 고정점 찾기 2022-06-13

import time
start_time = time.time()

from bisect import bisect_left, bisect_right

#n = int(input())
#data = list(map(int, input().split()))

n = 7
data = [-15,-4,3,8,9,13,15]

result = ''
for i in range(n):
    start = i
    end = n-i-1
    
    if start == data[start]:
        result = data[start]
        break
    elif end == data[end]:
        result = data[end]
        break
    
if result == '':
    print('-1')
else:
    print(result)
end_time = time.time()

print("time:", end_time - start_time)

 

 

[시간제한]

 

시간 제한 1초 통과