알고리즘 :: 이것이 코딩 테스트다 :: 이진탐색 :: Q28 :: 고정점 찾기

문제

고정점이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미한다. 모든 원소가 오름차순으로 정렬된 수열에 고정점이 있다면 고정점을 출력하는 프로그램을 작성하시오. 단, O(logN)에 해결하시오.

문제접근

• 정렬된 수열과 O(logN)이라는 힌트를 기반으로 이진 탐색으로 풀어야 함을 알게된다.
• mid값을 조절하면서 수열(arr)을 이진 탐색할 때 만날 수 있는 경우는 총 4가지 경우다.
  1. $arr[mid] > (N-1)$ : 수열의 최대 인덱스 번호를 넘어서는 경우
     • 왼쪽 부분을 탐색해야 한다.
  2. $arr[mid] < 0$ : 수열의 최소 인덱스 번호를 넘어서는 경우
     • 오른쪽 부분을 탐색해야 한다.
  3. $arr[mid] < mid$ : mid 인덱스의 요소가 mid보다 작은 경우
     • 오른쪽 부분을 탐색해야 한다.
     • 왜냐하면, 이미 arr[mid]가 mid 보다 작기 때문에 왼쪽 부분에서는 무조건 mid보다 작은 요소밖에 나올 수 없다. (정렬된 수열이기 때문이다.)
  4. $arr[mid] > mid$ : mid 인덱스의 요소가 mid보다 큰 경우
     • 왼쪽 부분을 탐색해야 한다.
     • 왜냐하면, 이미 arr[mid]가 mid 보다 크기 때문에 오른쪽 부분에서는 무조건 mid보다 큰 요소밖에 나올 수 없다. (정렬된 수열이기 때문이다.)

코드

#include <iostream>
using namespace std;

static int N, arr[1000000];

int solve(int left, int right) {
    if (left > right) return 0;     // 기저조건 1: left > right이면 고정점 없음.
    
    int mid = (left + right) / 2;
    if (N - 1 < arr[mid]) solve(left, mid - 1); // 기저조건 2: 불가능한 인덱스, 왼쪽으로 이동.
    if (arr[mid] < 0) solve(mid + 1, right);    // 기저조건 3: 불가능한 인덱스, 오른쪽으로 이동.
    
    if (mid == arr[mid]) return mid;
    else if (mid < arr[mid]) solve(left, mid - 1);  // x < [x] 이면 왼쪽으로 이동해야 함.
    else solve(mid + 1, right);     // x > [x] 이면 오른쪽으로 이동해야 함.
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> arr[i];
    
    int answer = solve(0, N - 1);
    if (answer) cout << answer << '\n';
    else cout << -1 << '\n';
}