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

  • 0
  • 0
0
0

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)

c. 🙄 회고

내 풀이

  • O(logN)이라서 이진탐색을 구현했다.

C. 🧐 문제 해설

이해한 내용을 바탕으로 작성했습니다.

a. 책 답안

python-for-coding-test/2.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.