문제 설명
정수 N이 주어졌을 때, 처음 N개의 자연수(1부터 N까지)로 만들 수 있는 좋은 순열(good permutation)을 찾는 것이 이 문제의 목표입니다.
순열(permutation)이란 어떤 집합의 전체 또는 일부 원소를 특정 순서에 따라 나열한 것을 의미합니다.
좋은 순열은 다음 조건을 모두 만족하는 순열입니다.
- 모든 원소에 대해 1 ≤ i ≤ N일 때 P(P(i)) = i 를 만족할 것
- 동시에 P(i) ≠ i, 즉 어떤 원소도 자기 자신의 위치에 있지 않을 것
쉽게 말해, 임의의 원소를 두 번 치환하면 반드시 원래 값으로 돌아오되, 한 번 치환했을 때는 반드시 다른 값으로 바뀌어야 합니다.
예시
입력 : N = 1
출력 : -1
N = 1인 경우에는 위 조건을 만족하는 순열이 존재하지 않으므로 -1을 출력해야 합니다.
해결 접근 방법
가장 간단한 풀이는 인접한 두 수를 짝지어 서로 교환하는 것입니다. 즉, 1과 2를 바꾸고, 3과 4를 바꾸는 방식으로 나아가면 됩니다.
이렇게 하면 p(2i) = 2i − 1, p(2i − 1) = 2i가 되어, 모든 원소가 두 번 치환 시 원래 값으로 돌아오면서도 어느 원소도 제자리에 있지 않게 됩니다.
단, N이 홀수라면 원소들을 두 개씩 완전히 짝지을 수 없어 유효한 순열이 성립하지 않습니다. 따라서 N이 홀수이면 -1을 출력하고, 짝수일 때만 위 방식으로 답을 구성합니다.
C++ 구현 예제
다음 프로그램은 위에서 설명한 풀이의 동작을 보여줍니다.
#include <iostream>
using namespace std;
void printGoodPermutation(int n) {
if (n % 2 != 0)
cout << -1;
else
for (int i = 1; i <= n / 2; i++)
cout << (2 * i) << "\t" << ((2 * i) - 1) << "\t";
}
int main() {
int n = 4;
cout << "Good Permutation of first N natural Numbers : \n";
printGoodPermutation(n);
return 0;
}
출력 결과
Good Permutation of first N natural Numbers :
2 1 4 3
복잡도 분석 및 마무리
이 풀이는 N의 홀짝 여부만 판단한 뒤 한 번의 순회로 결과를 출력하므로, 시간 복잡도는 O(N), 추가 공간 복잡도는 O(1)입니다. 별도의 탐색이나 백트래킹 없이도 규칙적인 교환만으로 최적의 해를 얻을 수 있는 대표적인 그리디 유형 문제입니다.