문제 소개
숫자 목록 row가 주어졌다고 가정해 보겠습니다. 이 목록은 일렬로 놓여 있는 양말들을 나타내며, 현재는 정렬되어 있지 않습니다. 우리의 목표는 각 양말 쌍이 (0, 1), (2, 3), (4, 5)처럼 서로 나란히 위치하도록 재배열하는 것이고, 이때 필요한 최소 스왑(교환) 횟수를 구해야 합니다.
예를 들어 입력이 row = [0, 5, 6, 2, 1, 3, 7, 4]라면 출력은 2가 됩니다. 실제 정렬 과정은 다음과 같습니다.
- [0, 5, 6, 2, 1, 3, 7, 4]
- [0, 1, 6, 2, 5, 3, 7, 4]
- [0, 1, 3, 2, 5, 6, 7, 4]
- [0, 1, 3, 2, 5, 4, 7, 6]
접근 방법: 유니온-파인드(Union-Find)
이 문제는 그래프 관점에서 바라보면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 양말 번호를 2로 나눈 값(짝 번호)이 같은 양말들은 하나의 그룹으로 묶습니다.
- 현재 배열에서 인접한 두 자리(짝수 번째 위치와 홀수 번째 위치)에 놓인 양말들이 속한 짝 그룹을 유니온-파인드로 연결합니다.
- 연결된 컴포넌트의 크기가 k라면, 해당 컴포넌트 전체를 올바른 위치에 배치하는 데 최소 k-1번의 스왑이 필요합니다.
알고리즘 단계
- 부모 배열
p와 집합 크기 배열sz를 선언합니다. find(u): u의 루트 노드를 찾는 함수입니다.p[u] == u이면 u를 반환하고, 그렇지 않으면 경로 압축(path compression)을 적용하며 재귀적으로 루트를 찾습니다.join(u, v): 두 노드가 속한 집합을 합치는 함수입니다. 이미 같은 집합이면 아무 작업도 하지 않고, 크기가 큰 집합 쪽에 작은 집합을 붙입니다.- n을 배열 길이의 절반(양말 짝의 개수)으로 설정하고,
p는 자기 자신으로 초기화하며sz는 모두 1로 채웁니다. - 각 인접 위치 쌍에 대해
u = arr[2i] / 2,v = arr[2i + 1] / 2를 계산한 뒤join(u, v)로 연결합니다. - 마지막으로
find(i) == i인 모든 루트에 대해sz[i] - 1을 더한 값을 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
vector<int> p, sz;
int find(int u) {
return p[u] == u ? u : p[u] = find(p[u]);
}
void join(int u, int v) {
int pu = find(u), pv = find(v);
if (pu == pv)
return;
if (sz[pu] >= sz[pv]) {
p[pv] = pu;
sz[pu] += sz[pv];
} else {
p[pu] = pv;
sz[pv] += sz[pu];
}
}
int solve(vector<int>& arr) {
int n = arr.size() / 2;
p = vector<int>(n);
for (int i = 0; i < n; ++i)
p[i] = i;
sz = vector<int>(n, 1);
for (int i = 0; i < n; ++i) {
int u = arr[i << 1] / 2;
int v = arr[i << 1 | 1] / 2;
join(u, v);
}
int ans = 0;
for (int i = 0; i < n; ++i)
if (find(i) == i)
ans += sz[i] - 1;
return ans;
}
int main() {
vector<int> v = {0, 5, 6, 2, 1, 3, 7, 4};
cout << solve(v);
}실행 결과
입력: [0, 5, 6, 2, 1, 3, 7, 4]
출력: 2
이 알고리즘은 거의 선형 시간에 동작하므로 배열의 크기가 커져도 효율적으로 최소 스왑 횟수를 계산할 수 있습니다.