문제 소개
두 개의 정수 n과 k가 주어졌을 때, 1부터 n까지의 숫자를 모두 사용하여 정확히 k개의 피크(peak, 봉우리)를 가지는 순열 A를 구성해야 합니다.
여기서 인덱스 i가 배열 A의 피크라는 것은 다음 조건을 만족할 때를 의미합니다.
- A[i] > A[i-1]
- A[i] > A[i+1]
즉, 해당 위치의 값이 양쪽 이웃 값보다 모두 커야 합니다. 만약 조건을 만족하는 순열을 만드는 것이 불가능하다면 -1을 반환해야 합니다.
예를 들어 n = 5, k = 2가 입력으로 주어지면 출력은 [2, 4, 1, 5, 3]이 될 수 있습니다. 물론 이 외에도 조건을 만족하는 다른 답들이 존재할 수 있습니다.
접근 방법
이 문제를 해결하기 위해 다음과 같은 아이디어를 사용합니다.
1. 피크 개수의 상한 확인
피크는 서로 인접할 수 없습니다. 두 개의 연속된 위치가 모두 피크가 되려면 각각의 값이 서로보다 커야 하므로 모순이 발생하기 때문입니다. 따라서 가능한 최대 피크 개수는 (n - 1) / 2입니다. k가 이 값을 초과하면 -1을 출력하고 종료합니다.
2. 인접 원소 교환으로 피크 생성
먼저 배열을 [1, 2, 3, ..., n] 형태의 오름차순 순열로 초기화한 뒤, 인덱스 2부터 시작하여 2칸씩 건너뛰며 인접한 두 원소를 교환합니다. 이렇게 하면 교환이 일어난 지점마다 피크가 하나씩 생기며, 총 k번의 교환으로 정확히 k개의 피크를 가진 순열을 얻을 수 있습니다.
알고리즘 의사 코드
if k > (n - 1) / 2, then:
return -1
크기가 101인 배열 a 선언
i := 1부터 n까지 반복:
a[i] := i
i := 2부터 2 * k까지 2씩 증가하며 반복:
a[i]와 a[i + 1]을 교환
i := 1부터 n까지 반복하며 a[i] 출력
C++ 구현 예제
아래는 위 알고리즘을 실제로 구현한 C++ 코드입니다.
#include <bits/stdc++.h>
using namespace std;
void solve(int n, int k) {
// 피크 개수가 최대치를 넘으면 불가능
if (k > (n - 1) / 2) {
cout << "-1";
return;
}
int a[101];
// 배열을 1부터 n까지의 오름차순으로 초기화
for (int i = 1; i <= n; i++)
a[i] = i;
// 인접 원소를 교환하여 피크 생성
for (int i = 2; i <= 2 * k; i += 2) {
swap(a[i], a[i + 1]);
}
// 결과 출력
for (int i = 1; i <= n; i++)
cout << a[i] << ", ";
}
int main() {
int n = 5;
int k = 2;
solve(n, k);
}
실행 결과
입력
5, 2
출력
1, 3, 2, 5, 4,
출력 결과를 살펴보면 인덱스 2의 값 3은 앞의 1보다 크고 뒤의 2보다 크며, 인덱스 4의 값 5 역시 앞의 2보다 크고 뒤의 4보다 큽니다. 따라서 정확히 2개의 피크를 가진 순열이 완성되었습니다.
복잡도 분석
배열 초기화와 교환, 출력 과정 모두 배열을 한 번씩 순회하므로 시간 복잡도는 O(n)입니다. 추가로 사용하는 공간은 배열 하나뿐이므로 공간 복잡도 역시 O(n)입니다.