길이가 같은 0이 아닌 두 개의 정수 수열 A와 B가 있다고 가정해 봅시다. 우리는 A[i]와 B[i]의 원소를 서로 교환(swap)할 수 있으며, 이때 두 원소는 각각의 수열에서 반드시 동일한 인덱스 위치에 있어야 합니다. 몇 번의 스왑을 거친 후, A와 B 두 수열 모두 엄격하게 증가(strictly increasing)하는 상태가 되어야 합니다. 목표는 이 조건을 만족하기 위한 최소 스왑 횟수를 구하는 것입니다.
문제 예시
예를 들어 입력이 A = [1, 3, 5, 4], B = [1, 2, 3, 7]이라면, 정답은 1입니다. A[3]과 B[3]을 서로 교환하면 A = [1, 3, 5, 7], B = [1, 2, 3, 4]가 되어 두 수열 모두 엄격하게 증가하게 되기 때문입니다.
해결 접근 방식: 동적 계획법(DP)
이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 각 인덱스에서 '스왑한 경우'와 '스왑하지 않은 경우'의 최소 비용을 추적하면 됩니다.
알고리즘 단계
- n := 배열 A의 크기로 설정하고, 크기가 n인 두 배열 swapCnt와 noSwapCnt를 생성합니다.
- swapCnt[0]에는 1(첫 원소를 스왑한 경우), noSwapCnt[0]에는 0(스왑하지 않은 경우)을 저장합니다.
- i를 1부터 n-1까지 순회하며 다음을 수행합니다:
- swapCnt[i] := n, noSwapCnt[i] := n으로 초기화합니다.
- 만약 A[i] > A[i-1] 그리고 B[i] > B[i-1]이라면 (교환 없이도 증가 유지 가능):
- noSwapCnt[i] := noSwapCnt[i-1]
- swapCnt[i] := swapCnt[i-1] + 1
- 만약 A[i] > B[i-1] 그리고 B[i] > A[i-1]이라면 (교환해도 증가 유지 가능):
- swapCnt[i] := min(swapCnt[i], 1 + noSwapCnt[i-1])
- noSwapCnt[i] := min(swapCnt[i-1], noSwapCnt[i])
- 최종적으로 min(swapCnt[n-1], noSwapCnt[n-1])을 반환합니다.
C++ 구현 예제
아래 구현 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minSwap(vector<int>& A, vector<int>& B) {
int n = A.size();
vector <int> swapCnt(n), noSwapCnt(n);
swapCnt[0] = 1;
noSwapCnt[0] = 0;
for(int i = 1; i < n; i++){
swapCnt[i] = n;
noSwapCnt[i] = n;
if(A[i] > A[i - 1] && B[i] > B[i - 1]){
noSwapCnt[i] = noSwapCnt[i - 1];
swapCnt[i] = swapCnt[i - 1] + 1;
}
if(A[i] > B[i - 1] && B[i] > A[i - 1]){
swapCnt[i] = min(swapCnt[i], 1 + noSwapCnt[i - 1]);
noSwapCnt[i] = min(swapCnt[i - 1], noSwapCnt[i]);
}
}
return min(swapCnt[n - 1], noSwapCnt[n - 1]);
}
};
main(){
vector<int> v1 = {1,3,5,4};
vector<int> v2 = {1,2,3,7};
Solution ob;
cout << (ob.minSwap(v1, v2));
}입력
[1,3,5,4] [1,2,3,7]
출력
1
마무리
이 알고리즘은 각 위치에서 스왑 여부에 따른 상태를 DP 배열로 관리하므로, 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)입니다. 두 수열의 관계(그대로 유지 가능 여부, 교환 가능 여부)를 매 단계마다 확인하면서 최적의 선택을 누적해 나가는 것이 핵심입니다. 이러한 패턴은 유사한 최적화 문제에서도 널리 활용되므로 잘 익혀두면 좋습니다.