[이코테][Java] 고정점 찾기

문제 설명

고정점이란, 수열의 원소 중에서 원소 값 = 원소의 인덱스 인 원소를 말한다.

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

하나의 수열이 N개의 서로 다른 원소를 포함하고 있고 오름차순으로 정렬되어 있을 때, 이 수열에서 고정점을 출력하는 프로그램을 작성하세요

고정점은 최대 1개만 존재하고, 만약 없다면 -1 출력

시간복잡도 O(log N)으로 알고리즘을 설계하지 않으면 '시간초과 판정'

 

입력조건

• 첫째 줄에 N
• 둘째 줄에 N개의 원소

출력조건

• 고정점 출력. 없으면 -1

입출력 예시

입력예시	출력예시
5 -15 -6 1 3 7	3
7 -15 -4 2 8 9 13 15	2
7 -15 -4 3 8 9 13 15	-1

 

 

 

 

문제 풀이

• 이진탐색을 수행해서 고정점을 찾는다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static int search_fixed_point(int[] array, int start, int end) {
        while (start <= end) {
            int mid = (start + end) / 2;    //중간값(=인덱스)

            if (array[mid] == mid) {    //원소값과 그 인덱스값이 같으면 고정점
                return mid;
            } else if (array[mid] < mid) {	//원소값 < 인덱스 이면 왼쪽 확인
                start = mid + 1;
        	} else {	//원소값 > 인덱스 이면 오른쪽 확인
                end = mid - 1;
            }
        }
        return -1;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));

        int n = Integer.parseInt(br.readLine());

        int[] array = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            array[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(search_fixed_point(array, 0, n));
    }
}

---

 

[참고서적]

이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈