Algorithm

[Algorithm] 고정점 찾기

씬프 2021. 6. 19. 09:24
반응형

문제

고정점이란 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미한다.

하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 원소가 오름차순으로 정렬되어 있다.

이 수열에서 고정점이 1개 존재할 때, 고정점을 출력하시오. 없다면 -1을 출력하시오.

 

풀이

완전 탐색으로 풀 수 있지만, 정렬되어있는 수열에서는 이진검색트리를 사용하는 것이 효율적이다.

해당 문제는 중간값과 중간 인덱스를 비교해 같은 값이라면 고정점으로 출력한다.

만약 아니라면 중간값 > 중간인덱스 일 때, 중간보다 뒷 부분 (start = mid + 1)을 탐색하고,

반대의 경우 앞 부분 (end = mid)을 탐색하도록 한다.

 

중간 값이 1이고, 중간 인덱스가 2인 경우 1보다 앞 선 값들은 1보다 작은 값인데, 인덱스는 0과 1밖에 없어 고정점이 나올 수 없다. 그렇기 때문에 뒷부분의 값을 확인하는 것이 맞다.

 

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int start = 0;
        int end = n;
        int fix = -1;
        while (start < end) {
            int mid = (start + end) / 2;
            if (arr[mid] == mid) fix = mid;
            if (arr[mid] < mid) start = mid + 1;
            else end = mid;
        }
        System.out.println(fix);
    }
        
}

'Algorithm' 카테고리의 다른 글

[Algorithm] 금광  (0) 2021.06.21
[Algorithm] 공유기 설치  (0) 2021.06.20
[Algorithm] 정렬된 배열에서 특정 수의 개수 구하기  (0) 2021.06.18
[Algorithm] 카드 정렬하기  (0) 2021.06.17
[Algorithm] 안테나  (0) 2021.06.16