15-2. 고정점 찾기

1. 문제

고정점Fixed Point이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미합니다. 예를 들어 수열 a = {-15, -4, 2, 8, 13}이 있을 때 a[2]=2이므로, 고정점은 2가 됩니다.
하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 원소가 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 고정점이 있다면, 고정점을 출력하는 프로그램을 작성하세요. 만약 고정점이 없다며녀 -1을 출력합니다.
단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다.

2. 입력

• 첫째 줄에 N이 입력됩니다. (1≤N≤1,000,000)
  이상 기호를 찾았다
• 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다. (-10^9≤각 원소의 값 ≤10^9)
  지수는 못 찾았다. 숫자를 필요할 때마다 입력해줘야 할 것 같은데 귀찮다
10개월이 지난 지금도 못 찾았다.

3. 출력

• 고정점을 출력한다. 고정점이 없다면 -1을 출력합니다.

4. 풀이

• 서로 다른 원소 오름차순 정렬 두 가지 키워드를 가지고 인덱스와 값의 관계를 따져보았다.
• arr[i] < i: 인덱스가 해당 배열의 값보다 큰 경우, i보다 작은 인덱스는 아무리 노력을 해도 고정점이 될 수 없다.
  이런 게 태생적 한계인가... 내 머리로 알고리즘 머신이 안 되는 건 태생적 한계가 아닐까...
• 반대의 경우도 마찬가지

5. 처음 코드와 달라진 점

• 코드가 달라진 점은 특별히 없고 의문점이 하나 있다.
• 현재 코드는 arr[i]==i 일 때 i를 return한다.
• 근데 고정점이 하나만 있으라는 법은 없는데 현재는 하나만 리턴한다.
• 따로 온라인 저지에 올라온 것도 없어서 테스트가 불가능하다.
• 그래서 저자가 올린 깃허브를 봤는데 마찬가지였다.
• 질문을 올린 상태라서 알게 된다면 수정하겠다.

💡 21.08.06 추가) 고정점은 최대 하나라는 답변을 받았다.
약 10개월이 지난 지금 풀고 있었는데 똑같은 생각으로 고정점 개수를 구하고 있었다.
사람은 바뀌지 않는다.

6. 코드

#include <iostream>
#include <vector>
using namespace std;

vector<int> arr;

int binarySearch(int start, int end) {
	while (start <= end){
		int mid = (start + end) / 2;
		if (arr[mid] == mid) return mid;
		if (arr[mid] > mid) end = mid - 1;
		else start = mid + 1;
	}
	return -1;
}


int main() {
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		arr.push_back(tmp);
	}

	cout << binarySearch(0, n - 1) << endl;
}