문제 소개
N쌍의 커플이 일렬로 배치된 2N개의 좌석에 앉아 있고, 모든 커플이 서로 손을 잡을 수 있도록 나란히 앉으려고 합니다. 우리가 구해야 하는 값은 모든 커플을 옆자리에 앉히기 위해 필요한 최소 교환(swap) 횟수입니다.
사람과 좌석은 0부터 2N-1까지의 번호로 표현되며, 커플에게는 순서대로 번호가 부여됩니다. 첫 번째 커플은 (0, 1), 두 번째 커플은 (2, 3)처럼 짝지어지고, 마지막 커플은 (2N-2, 2N-1)이 됩니다.
커플의 초기 자리 배치는 배열 row로 주어집니다. 여기서 row[i]는 i번째 좌석에 처음 앉아 있는 사람의 번호를 의미합니다.
예를 들어 입력이 [0, 2, 4, 1, 3, 5]라면 정답은 2입니다. 단 두 번의 교환만으로 모든 커플이 나란히 앉도록 만들 수 있습니다.
해결 접근법: 유니온-파인드(Union-Find)
이 문제는 유니온-파인드(서로소 집합, DSU) 자료구조를 활용하면 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 사람 번호를 2로 나누면(a / 2) 해당 사람이 속한 커플 그룹 번호를 얻을 수 있습니다.
- 인접한 두 좌석(짝수 번째 좌석과 바로 다음 좌석)에 앉은 두 사람의 커플 그룹을 유니온 연산으로 하나로 합칩니다.
- 모든 좌석 쌍을 처리한 뒤, 전체 커플 수 N에서 남아 있는 집합(연결 요소)의 개수를 빼면 최소 교환 횟수가 됩니다.
그 이유는 간단합니다. 크기가 k인 연결 요소 안에서 커플을 모두 맞추려면 k-1번의 교환이 필요하므로, 전체 교환 횟수는 Σ(k-1) = N - (연결 요소 개수)와 같아지기 때문입니다.
알고리즘 단계
- UF 클래스 정의: parent 배열과 현재 집합 개수를 저장하는 count 변수를 가집니다.
- 초기화: count := N으로 설정하고, parent[i] := i로 만들어 각 원소가 자기 자신을 루트로 가지도록 합니다.
- getParent(i): parent[i]가 i와 같으면 i를 반환하고, 그렇지 않으면 경로 압축(path compression)을 적용하면서 재귀적으로 루트를 찾습니다.
- unionn(a, b): 두 원소의 루트(parA, parB)가 같다면 아무 작업도 하지 않고, 다르다면 count를 1 감소시킨 뒤 parB의 부모를 parA로 설정하여 두 집합을 병합합니다.
- 메인 로직: n := row의 크기, N := n / 2로 설정하고 UF 객체를 생성합니다. 각 좌석 쌍(gr * 2, gr * 2 + 1)에 앉은 사람 a, b에 대해 uf.unionn(a / 2, b / 2)를 호출합니다.
- 결과 반환: N - uf.count를 반환합니다.
C++ 구현 예제
아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
class UF{
public:
vector<int> parent;
int count;
UF(int N){
count = N;
parent = vector<int>(N);
for (int i = 0; i < N; i++) {
parent[i] = i;
}
}
void unionn(int a, int b){
int parA = getParent(a);
int parB = getParent(b);
if (parA == parB)
return;
count--;
parent[parB] = parA;
}
int getParent(int i){
if (parent[i] == i)
return i;
return parent[i] = getParent(parent[i]);
}
};
int minSwapsCouples(vector<int>& row) {
int n = row.size();
int N = n / 2;
UF uf(N);
for (int gr = 0; gr < N; gr++) {
int a = row[gr * 2];
int b = row[gr * 2 + 1];
uf.unionn(a / 2, b / 2);
}
return N - uf.count;
}
};
main(){
Solution ob;
vector<int> v = {0,2,4,1,3,5};
cout << (ob.minSwapsCouples(v));
}
입력
{0,2,4,1,3,5}
출력
2
복잡도 분석
각 좌석 쌍마다 유니온 연산을 한 번씩 수행하므로 시간 복잡도는 O(N·α(N))입니다. 여기서 α는 아커만 함수의 역함수로, 사실상 상수로 취급됩니다. 공간 복잡도는 parent 배열 저장을 위해 O(N)입니다.