처음 N개의 자연수(1부터 N까지)가 주어졌을 때, 인접한 두 요소 간의 절대 차이가 항상 1보다 큰 순열(permutation)을 만드는 것이 우리의 과제입니다. 만약 그러한 순열이 존재하지 않는다면 -1을 반환해야 합니다.
이 문제는 그리디(Greedy) 알고리즘을 사용하면 아주 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 모든 홀수를 오름차순 또는 내림차순으로 먼저 나열합니다.
- 그다음 모든 짝수를 내림차순 또는 오름차순으로 이어서 나열합니다.
홀수끼리의 차이는 최소 2이고, 짝수끼리의 차이 역시 최소 2이며, 마지막 홀수와 첫 번째 짝수 사이의 차이도 2 이상이 되므로 전체 수열에서 인접 요소 간 절대 차이가 항상 1보다 크게 됩니다.
알고리즘: arrangeN(n)
Begin
if N == 1, then return 1
if N == 2 or 3, then return -1
even_max와 odd_max를 N 이하의 최대 짝수와 홀수로 설정
모든 홀수를 내림차순으로 출력
모든 짝수를 내림차순으로 출력
End알고리즘 설명
- N이 1이라면 순열은 "1" 하나뿐이므로 그대로 반환합니다.
- N이 2 또는 3인 경우에는 조건을 만족하는 순열이 존재하지 않으므로 -1을 출력합니다.
(예: N=2 → [1,2] 차이 1, N=3 → 어떤 순서로 배치해도 차이가 1인 인접 쌍이 반드시 발생) - N이 4 이상일 때는 N 이하의 최대 짝수(even_max)와 최대 홀수(odd_max)를 구합니다.
- 홀수를 가장 큰 값부터 2씩 감소시키며 출력하고, 이어서 짝수를 가장 큰 값부터 2씩 감소시키며 출력합니다.
C++ 구현 예제
#include <iostream>
using namespace std;
void arrangeN(int N) {
if (N == 1) { // N이 1이면 그 값 하나만 출력
cout << "1";
return;
}
if (N == 2 || N == 3) { // N = 2, 3인 경우 조건을 만족하는 순열 없음
cout << "-1";
return;
}
int even_max = -1, odd_max = -1;
// N 이하의 최대 짝수와 최대 홀수 찾기
if (N % 2 == 0) {
even_max = N;
odd_max = N - 1;
} else {
odd_max = N;
even_max = N - 1;
}
// 모든 홀수를 내림차순으로 출력
while (odd_max >= 1) {
cout << odd_max << " ";
odd_max -= 2;
}
// 모든 짝수를 내림차순으로 출력
while (even_max >= 2) {
cout << even_max << " ";
even_max -= 2;
}
}
int main() {
int N = 8;
arrangeN(N);
}실행 결과
7 5 3 1 8 6 4 2
결과 검증
출력된 수열 [7, 5, 3, 1, 8, 6, 4, 2]에서 인접 요소 간 절대 차이를 확인해 보면:
- |7−5| = 2, |5−3| = 2, |3−1| = 2 (홀수 구간)
- |1−8| = 7 (경계 지점)
- |8−6| = 2, |6−4| = 2, |4−2| = 2 (짝수 구간)
모든 인접 요소 간 절대 차이가 1보다 크므로 조건을 만족하는 올바른 순열임을 알 수 있습니다.
복잡도 분석
- 시간 복잡도: O(N) — 각 숫자를 한 번씩만 방문하여 출력합니다.
- 공간 복잡도: O(1) — 추가적인 배열 없이 상수 개의 변수만 사용합니다.