문제 이해하기
길이가 같은 두 개의 숫자 리스트 A와 B가 주어져 있다고 가정해 보겠습니다. 또한 각 원소가 [i, j] 형태인 2차원 리스트 C가 주어지는데, 이는 A[i]와 A[j]를 원하는 만큼 자유롭게 교환(swap)할 수 있음을 의미합니다. 우리가 구해야 하는 것은 교환 작업을 마친 후 A[i] = B[i]를 만족하는 쌍의 최대 개수입니다.
예를 들어 입력이 다음과 같다면,
A = [5, 6, 7, 8], B = [6, 5, 8, 7], C = [[0, 1], [2, 3]]
정답은 4가 됩니다. A[0]과 A[1]을 교환하고, A[2]와 A[3]을 교환하면 네 개의 인덱스 모두에서 A[i] = B[i]가 성립하기 때문입니다.
해결 전략: 연결 요소 활용
이 문제의 핵심은 그래프의 연결 요소(Connected Component) 개념입니다. 교환이 가능한 인덱스 쌍들을 간선으로 보고 그래프를 만들면, 같은 연결 요소에 속한 인덱스들끼리는 임의의 순열로 값을 재배열할 수 있습니다. 따라서 각 연결 요소 안에서 A의 값들이 B의 값들과 몇 개나 짝지어질 수 있는지 세어 더하면 정답을 얻을 수 있습니다.
알고리즘을 단계별로 정리하면 다음과 같습니다.
- N := 리스트 A의 크기
- graph := 주어진 간선들을 양방향으로 연결해 만든 그래프
- ans := 0 (정답 카운터)
- seen := 크기 N의 방문 여부 리스트(False로 초기화)
- u를 0부터 N-1까지 순회하며 다음을 수행합니다.
- seen[u]가 False라면, queue에 u를 넣고 seen[u]를 True로 설정합니다.
- BFS(너비 우선 탐색)로 u와 연결된 모든 노드를 큐에 추가하며 방문 처리합니다.
- count := 큐에 속한 인덱스 i들에 대한 B[i] 값의 빈도수 맵(Counter)
- 큐의 각 인덱스 i에 대해 count[A[i]]가 남아 있다면 해당 값을 1 감소시키고 ans를 1 증가시킵니다.
- 모든 순회가 끝나면 ans를 반환합니다.
같은 연결 요소 내부에서는 어떤 위치로든 값을 옮길 수 있으므로, 위와 같은 단순한 빈도수 매칭(탐욕적 매칭)만으로도 각 그룹에서 만들 수 있는 최대 일치 쌍을 정확히 계산할 수 있습니다.
구현 예제
from collections import Counter
class Solution:
def solve(self, A, B, edges):
N = len(A)
graph = [[] for _ in range(N)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
ans = 0
seen = [False] * N
for u in range(N):
if not seen[u]:
queue = [u]
seen[u] = True
# BFS로 연결 요소의 모든 인덱스를 수집
for node in queue:
for nei in graph[node]:
if not seen[nei]:
queue.append(nei)
seen[nei] = True
# 컴포넌트 내 B값의 빈도수 계산
count = Counter(B[i] for i in queue)
# A값과 매칭되는 만큼 정답 증가
for i in queue:
if count[A[i]]:
count[A[i]] -= 1
ans += 1
return ans
ob = Solution()
A = [5, 6, 7, 8]
B = [6, 5, 8, 7]
C = [[0, 1], [2, 3]]
print(ob.solve(A, B, C))입력
[5, 6, 7, 8], [6, 5, 8, 7], [[0, 1], [2, 3]]
출력
4
복잡도 분석
시간 복잡도는 그래프 생성과 BFS 순회에 O(N + E)(E는 간선의 개수), 각 컴포넌트의 빈도수 계산 및 매칭에 선형 시간이 소요되므로 전체적으로 O(N + E)입니다. 공간 복잡도는 인접 리스트, 방문 배열, 큐 저장에 O(N + E)입니다.