반응형
문제
고정점이란 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미한다.
하나의 수열이 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 |