문제 설명
0부터 N-1까지의 N개 원소로 이루어진 순열(permutation)이 주어집니다. 여기서 고정점(fixed point)이란 값이 해당 인덱스와 일치하는 위치, 즉 arr[i] = i를 만족하는 인덱스를 의미합니다.
배열에서 최대 1번의 스왑(원소 교환)을 수행할 수 있을 때, 만들 수 있는 고정점의 최대 개수를 구하는 것이 이 문제의 목표입니다.
예시
입력 배열이 {0, 1, 2, 3, 4, 6, 5}라고 가정해 보겠습니다. 이때 정답은 7입니다.
- 모든 원소를 고정점으로 만들기 위해서는 6과 5의 위치를 서로 교환해야 합니다.
- 교환이 완료되면 배열의 모든 원소가 고정점이 되며, 고정점의 최대 개수는 7이 됩니다.
알고리즘 접근 방법
효율적인 해결을 위해 다음과 같은 단계로 접근할 수 있습니다.
- 입력 배열의 각 원소가 어느 위치에 있는지 저장하는 배열
pos를 생성합니다. 즉,pos[arr[i]] = i형태로 값을 기록합니다. - 배열을 처음부터 끝까지 순회하면서 아래 두 가지 경우를 처리합니다.
arr[i] == i인 경우: 이미 고정점이므로 count를 1 증가시키고 다음 원소로 넘어갑니다.pos[i] == arr[i]인 경우: 두 원소를 교환하면 i와 arr[i]가 동시에 고정점이 되어 count가 2 증가합니다. 단, 스왑은 최대 한 번만 가능하다는 점을 반드시 기억해야 합니다.
- 순회가 끝날 때까지 스왑을 수행하지 않았다면, 교환으로 count를 2 늘릴 수 있는 경우가 없었음을 의미합니다. 이때 고정점이 아닌 원소가 2개 이상 남아 있다면, 한 번의 스왑으로 count를 1 증가시켜 그중 하나를 고정점으로 만들 수 있습니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
int getMaximumFixedPoints(int arr[], int n) {
int i, pos[n], count = 0, swapped = 0;
// 각 원소의 위치를 pos 배열에 저장
for (i = 0; i < n; i++)
pos[arr[i]] = i;
for (i = 0; i < n; i++) {
if (arr[i] == i) {
// 이미 고정점인 경우
count++;
} else if (swapped == 0 && pos[i] == arr[i]) {
// 한 번의 스왑으로 두 개의 고정점을 얻는 경우
count += 2;
swapped = 1;
}
}
// 스왑하지 못했고, 고정점이 아닌 원소가 2개 이상 남은 경우
if (swapped == 0 && count < n - 1) {
count++;
}
return count;
}
int main() {
int arr[] = {0, 1, 2, 3, 4, 6, 5};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum value of fixed point = " << getMaximumFixedPoints(arr, n) << endl;
return 0;
}실행 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.
Maximum value of fixed point = 7
복잡도 분석
- 시간 복잡도: O(N) — 배열을 두 번 순회하므로 입력 크기에 비례합니다.
- 공간 복잡도: O(N) — 각 원소의 위치를 저장하기 위한 추가 배열 pos가 필요합니다.