N개의 정수로 이루어진 배열 a[]가 주어졌을 때, 인덱스들의 순열 중에서 해당 인덱스에 위치한 값들이 비내림차순(바로 앞의 값보다 작아지지 않는 순서)을 이루도록 만드는 서로 다른 순열 k개를 출력하는 것이 이 문제의 목표입니다. 조건을 만족하는 순열을 k개 만드는 것이 불가능하다면 -1을 출력합니다.
예시
입력: arr[] = {2,5,6,2,2,2,2}, k = 4
출력:
0 3 4 5 6 1 2
3 0 4 5 6 1 2
0 3 4 5 6 1 2
3 0 4 5 6 1 2
풀이의 핵심은 배열을 정렬하면서 각 원소의 원래 인덱스를 함께 기록하는 것입니다. 이렇게 하면 첫 번째 순열을 바로 얻을 수 있습니다. 이후 정렬된 배열에서 값이 서로 같은 인접한 두 원소를 찾아 자리를 맞바꾸면, 전체 수열은 여전히 비내림차순을 유지하면서 새로운 순열을 하나 더 만들 수 있습니다. 같은 방법을 반복하면 세 번째, 네 번째 순열도 차례대로 생성할 수 있습니다.
접근 방법
정렬이 끝난 뒤 인접한 원소끼리 값이 같은 경우의 수를 셉니다. 이 개수에 1을 더한 값이 요청된 k보다 작으면 서로 다른 순열 k개를 만들 수 없으므로 -1을 출력하고 종료합니다. 반대로 충분하다면, 매 단계마다 현재 순열을 출력한 뒤 값이 같은 인접한 쌍 하나를 골라 교환하는 작업을 k-1번 반복하고 마지막 순열을 한 번 더 출력합니다.
알고리즘
시작
1단계 -> 함수 void indice(int n, pair<int, int> array[]) 선언
int i = 0부터 i < n까지 i를 1씩 증가시키며 반복
array[i].second 출력
반복문 끝
2단계 -> 함수 void permutation(int n, int a[], int k) 선언
STL pair<int, int> arr[n] 사용
int i = 0부터 i < n까지 반복
arr[i].first에 a[i] 대입
arr[i].second에 i 대입
반복문 끝
sort(arr, arr + n) 호출
int count를 1로 초기화
int i = 1부터 i < n까지 반복
IF (arr[i].first == arr[i - 1].first)
count 1 증가
End
반복문 끝
IF count < k
-1 반환
End
int i = 0부터 i < k - 1까지 반복
indice(n, arr) 호출
int j = 1부터 j < n까지 반복
IF arr[j].first == arr[j - 1].first
swap(arr[j], arr[j - 1]) 호출
Break
End
반복문 끝
반복문 끝
indice(n, arr) 호출
3단계 -> main() 함수 내부
배열 a[] = {2,5,6,2,2,2,2} 선언
int n = sizeof(a)/sizeof(a[0]) 선언
int k = 4 선언
permutation(n, a, k) 호출
종료
구현 코드
아래 코드는 pair, sort, swap 등 C++ STL을 활용하므로 C++ 컴파일러로 빌드해야 합니다.
#include <bits/stdc++.h>
using namespace std;
void indice(int n, pair<int, int> array[]){
for (int i = 0; i < n; i++)
cout << array[i].second << " ";
cout << endl;
}
void permutation(int n, int a[], int k){
pair<int, int> arr[n];
for (int i = 0; i < n; i++){
arr[i].first = a[i];
arr[i].second = i;
}
sort(arr, arr + n);
int count = 1;
for (int i = 1; i < n; i++)
if (arr[i].first == arr[i - 1].first)
count++;
if (count < k){
cout << "-1";
return;
}
for (int i = 0; i < k - 1; i++){
indice(n, arr);
for (int j = 1; j < n; j++){
if (arr[j].first == arr[j - 1].first){
swap(arr[j], arr[j - 1]);
break;
}
}
}
indice(n, arr);
}
int main(){
int a[] ={2,5,6,2,2,2,2};
int n = sizeof(a) / sizeof(a[0]);
int k = 4;
permutation(n, a, k);
return 0;
}
실행 결과
위 프로그램을 컴파일해서 실행하면 다음과 같은 결과가 출력됩니다.
0 3 4 5 6 1 2 3 0 4 5 6 1 2 0 3 4 5 6 1 2 3 0 4 5 6 1 2