고정점 찾기 - 이것이 코딩 테스트다 with java

1. 문제

고정점이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미 합니다. 예를 들어 a = {-15, -4, 2, 8, 13} 이 있을 때 a[2] = 2이므로, 고정점은 2가 됩니다. 이때, 배열이 오름차순으로 정렬 되어 있을 때, 고정점을 출력 하시오. N개의 수열로 이루어져 있고, 둘째 줄에는 수열의 값이 주어집니다. 시간 복잡도는 O(logN) 으로 알고리즘을 설계 해야 합니다. (1 <= N <= 1,000,000)

 

2. 입력

5

-15 -6 1 3 7

 

3. 출력

3

 

 

4. 접근

1. 배열을 선형 탐색 시 시간 복잡도는 O(N)이 걸리므로, 이진탐색으로 O(logN)으로 해결 해야 합니다.

2. left = 0 인덱스의 최소값

3. right = n - 1 인덱스의 최대값 으로 초기화

4. 오름차순으로 정렬이 되어 있으므로 array[mid] > mid 라면, right의 범위를 줄이고

5. array[mid] < mid 라면, left의 범위를 늘려 mid의 범위를 좁혀 최적 답안을 반환 합니다.

 

 

5. java 소스 코드

public class Page368 {
    // 고정점 찾기
    public static void main(String[] args) {
//        int N = 5;
//        int N = 7;
        int N = 7;
//        int[] array = new int[]{-15, -6, 1, 3, 7};
//        int[] array = new int[]{-15, -4, 2, 8, 9, 13, 15};
        int[] array = new int[]{-15, -4, 3, 8, 9, 13, 15};
        System.out.print(new Page368().solution(N, array));
    }

    public int solution(int n, int[] array) {
        int result = -1;
        int left = 0;
        int right = n - 1;

        while(left <= right) {
            int mid = (left + right) / 2;

            if (array[mid] > mid) {
                // array[mid] 이상은 찾을수 없다
                right = mid - 1;
            } else if (array[mid] < mid) {
                // array[mid] 이하는 찾을수 없다
                left = mid + 1;
            } else {
                return mid;
            }
        }

        return result;
    }
}