cho.sh

완벽한 순열 2

순열 P가 주어질 때, 0에서 Q를 반복 적용하면 모든 인덱스를 한 번씩 방문하게 되는 순열 Q 중 P와 다른 위치가 가장 적은 것을 찾는다.

보통7조합론그리디수학구현아직 제출이 없습니다시간 제한2초메모리 제한128 MB

문제

0부터 N-1까지의 모든 정수를 정확히 한 번씩 포함하는 순열 A가 있다. A로부터 같은 길이의 배열 B를 다음과 같이 만든다.

  1. B[0] = 0
  2. B[i] = A[B[i-1]] (1 ≤ i ≤ N-1)

이렇게 얻은 B도 순열이면 A를 완벽한 순열이라고 부른다.

다음 표는 길이가 3인 모든 순열 A와 그 자식 배열 B를 보여 준다. {1, 2, 0}과 {2, 0, 1}은 B도 순열이므로 완벽한 순열이다.

AB
0, 1, 20, 0, 0
0, 2, 10, 0, 0
1, 0, 20, 1, 0
1, 2, 00, 1, 2
2, 0, 10, 2, 1
2, 1, 00, 2, 0

길이가 N인 순열 P가 주어진다. P와 차이가 가장 작은 완벽한 순열 Q를 출력하라. 두 순열의 차이는 P[i]와 Q[i]가 서로 다른 인덱스 i의 개수이다.

입력

첫째 줄에 순열의 크기 N (1 ≤ N ≤ 50)이 주어진다. 둘째 줄에 N개의 정수로 순열 P[0], P[1], ..., P[N-1]이 공백으로 구분되어 주어진다.

출력

P와의 차이가 최소인 완벽한 순열 Q를 한 줄에 출력한다. 그런 Q가 여러 개라면, Q의 자식 배열 B가 사전순으로 가장 앞서는 Q를 출력한다.