이 튜토리얼에서는 최대 k번의 스왑(swap)을 수행한 후 얻을 수 있는 가장 큰 순열을 찾는 프로그램을 작성해 보겠습니다.
문제 해결 접근 방식
이 문제의 핵심 아이디어는 간단합니다. 배열의 앞쪽부터 시작해서 각 자리에 가능한 한 가장 큰 숫자를 배치하는 것입니다. 이를 위해 각 원소의 현재 위치를 빠르게 조회할 수 있도록 위치 정보 배열을 활용합니다.
문제를 해결하는 단계는 다음과 같습니다.
- 배열을 초기화합니다.
- 각 원소의 인덱스를 저장하기 위해 크기가 n + 1인 위치 배열(position)을 초기화합니다.
- 배열을 순회하면서 각 원소의 인덱스를 position 배열에 저장합니다.
- i가 n보다 작고 k가 0보다 큰 동안 반복하는 루프를 작성합니다.
- n - i 값의 현재 위치를 임시 변수(temp)에 저장합니다.
- 현재 원소 arr[i]의 위치를 position[n - i] 값으로 갱신합니다.
- position[n - i] 값을 현재 인덱스 i로 갱신합니다.
- arr[temp]와 arr[i]를 서로 스왑합니다.
- k를 1 감소시킵니다.
- 최종 배열의 원소들을 출력합니다.
여기서 중요한 최적화 포인트는, 이미 해당 자리에 올바른 최댓값(n - i)이 놓여 있다면 스왑 없이 건너뛴다는 것입니다. 이렇게 하면 불필요한 스왑 횟수를 아낄 수 있어 제한된 k 안에 더 많은 자리를 최적화할 수 있습니다.
예제 코드
전체 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void getLargestPermutation(int arr[], int n, int k) {
int position[n + 1];
for (int i = 0; i < n; ++i) {
position[arr[i]] = i;
}
for (int i = 0; i < n && k; ++i) {
if (arr[i] == n - i) {
continue;
}
int temp = position[n - i];
position[arr[i]] = position[n - i];
position[n - i] = i;
swap(arr[temp], arr[i]);
--k;
}
}
int main() {
int arr[] = { 5, 3, 2, 6, 7, 1, 4 };
int n = 7, k = 3;
getLargestPermutation(arr, n, k);
for (int i = 0; i < n; ++i) {
cout << arr[i];
}
cout << endl;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
7653214
동작 과정 설명
입력 배열 {5, 3, 2, 6, 7, 1, 4}에서 k = 3일 때의 진행 과정을 살펴보겠습니다.
- 첫 번째 스왑: 첫 번째 자리에는 가장 큰 값인 7이 와야 합니다. 7은 현재 인덱스 4에 있으므로 arr[0]의 5와 스왑하여 배열은 {7, 3, 2, 6, 5, 1, 4}가 됩니다.
- 두 번째 스왑: 두 번째 자리에는 6이 와야 합니다. 6은 인덱스 3에 있으므로 arr[1]의 3과 스왑하여 {7, 6, 2, 3, 5, 1, 4}가 됩니다.
- 세 번째 스왑: 세 번째 자리에는 5가 와야 합니다. 5는 인덱스 4에 있으므로 arr[2]의 2와 스왑하여 {7, 6, 5, 3, 2, 1, 4}가 됩니다.
이제 k = 0이 되어 더 이상 스왑할 수 없으며, 최종 결과는 7653214입니다.
시간 복잡도
이 알고리즘의 시간 복잡도는 O(n)입니다. 위치 배열을 채우는 데 O(n), 스왑 루프 역시 최대 O(min(n, k))번만 순회하므로 전체적으로 선형 시간에 동작합니다. 공간 복잡도는 위치 배열을 저장하기 위해 O(n)이 필요합니다.
결론
이 튜토리얼에서는 그리디(greedy) 기법과 위치 조회 배열을 활용해 최대 k번의 스왑으로 만들 수 있는 가장 큰 순열을 효율적으로 구하는 방법을 알아보았습니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨 주세요.