문제 요약
크기가 50 × 50인 표가 있고, 처음에는 모든 셀이 비어 있다.
표에는 다음 명령을 수행할 수 있다.
UPDATE r c value
특정 셀의 값을 변경한다.
UPDATE value1 value2
값이 value1인 모든 셀을 value2로 변경한다.
MERGE r1 c1 r2 c2
두 셀을 하나의 셀처럼 병합한다.
UNMERGE r c
선택한 셀이 속한 병합 그룹을 모두 해제한다.
PRINT r c
선택한 셀의 값을 출력한다.PRINT 명령의 결과를 순서대로 배열에 담아 반환해야 한다.
핵심 아이디어
병합된 셀들은 어느 위치를 선택하더라도 같은 값에 접근해야 한다.
따라서 병합된 셀들을 하나의 집합으로 관리하는 Union-Find 자료구조를 사용한다.
각 병합 그룹에는 대표 셀이 하나 존재하며, 실제 값은 대표 셀에만 저장한다.
parent[i] = i번 셀이 속한 그룹의 부모
values[root] = 해당 병합 그룹의 값예를 들어 (1, 1)과 (1, 2)를 병합했다면 두 위치는 같은 대표 셀을 가진다.
find((1, 1)) == find((1, 2))두 셀 중 어느 위치를 선택해도 대표 셀을 찾은 뒤 같은 값을 읽거나 수정할 수 있다.
좌표를 번호로 변환하기
표는 2차원이지만 Union-Find 배열은 1차원으로 관리하는 것이 편리하다.
행과 열을 다음 공식으로 하나의 번호로 변환한다.
index = (row - 1) * 50 + (column - 1)행과 열은 1부터 시작하지만 배열 인덱스는 0부터 시작하므로 각각 1을 뺀다.
예를 들어 다음 좌표는 다음 번호로 변환된다.
(1, 1) -> 0
(1, 2) -> 1
(2, 1) -> 50
(50, 50) -> 2499전체 셀의 수는 다음과 같다.
50 × 50 = 2500Union-Find
Union-Find는 원소들이 같은 집합에 속해 있는지 확인하고, 서로 다른 두 집합을 합치는 자료구조다.
이 문제에서는 병합된 셀들의 그룹을 관리하는 데 사용한다.
find
선택한 셀이 속한 병합 그룹의 대표 셀을 찾는다.
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]대표 셀을 찾는 과정에서 부모를 대표 셀로 바로 연결하는 경로 압축을 적용한다.
union
두 셀이 속한 그룹을 하나로 합친다.
이 문제에서는 일반적인 union 함수보다 MERGE 명령 안에서 값의 우선순위까지 함께 처리하는 편이 이해하기 쉽다.
명령어 처리
UPDATE r c value
선택한 셀의 대표 셀을 찾고 대표 셀의 값을 변경한다.
cell = to_index(r, c)
root = find(cell)
values[root] = value병합된 그룹의 모든 셀은 같은 대표 셀을 바라보므로 그룹 전체의 값이 변경된다.
UPDATE value1 value2
모든 대표 셀을 확인하면서 값이 value1인 그룹의 값을 value2로 변경한다.
for cell in range(SIZE):
if parent[cell] == cell and values[cell] == value1:
values[cell] = value2값은 대표 셀에만 저장하므로 병합 그룹에 포함된 모든 셀을 개별적으로 변경할 필요가 없다.
MERGE r1 c1 r2 c2
먼저 두 셀의 대표 셀을 찾는다.
root1 = find(cell1)
root2 = find(cell2)두 대표 셀이 같다면 이미 같은 병합 그룹이므로 명령을 무시한다.
if root1 == root2:
continue병합된 셀이 가져야 할 값은 다음 규칙으로 결정한다.
첫 번째 셀에 값이 있으면 첫 번째 셀의 값 사용
첫 번째 셀이 비어 있으면 두 번째 셀의 값 사용
두 셀이 모두 비어 있으면 빈 값 사용merged_value = values[root1] or values[root2]파이썬에서 빈 문자열은 False로 처리되므로 위와 같이 간단하게 작성할 수 있다.
두 번째 그룹의 대표 셀을 첫 번째 그룹의 대표 셀 아래에 연결하고, 결정한 값을 첫 번째 대표 셀에 저장한다.
parent[root2] = root1
values[root1] = merged_value
values[root2] = ""UNMERGE r c
병합 해제는 이 문제에서 가장 주의해야 하는 명령이다.
먼저 선택한 셀이 속한 그룹의 대표 셀과 기존 값을 저장한다.
target = to_index(r, c)
root = find(target)
saved_value = values[root]그다음 같은 대표 셀을 가진 모든 셀을 찾는다.
members = [
cell
for cell in range(SIZE)
if find(cell) == root
]찾은 모든 셀을 각각 독립된 셀로 되돌리고 값을 비운다.
for cell in members:
parent[cell] = cell
values[cell] = ""마지막으로 병합 해제를 요청한 셀에만 기존 값을 저장한다.
values[target] = saved_value대표 셀이 아닌 셀에서 UNMERGE를 요청할 수도 있으므로 반드시 명령에 주어진 target에 값을 저장해야 한다.
PRINT r c
선택한 셀의 대표 셀을 찾은 뒤 값을 확인한다.
value = values[find(cell)]값이 비어 있으면 "EMPTY"를 출력한다.
answer.append(value if value else "EMPTY")Python 코드
def solution(commands):
TABLE_SIZE = 50
CELL_COUNT = TABLE_SIZE * TABLE_SIZE
parent = list(range(CELL_COUNT))
values = [""] * CELL_COUNT
answer = []
def to_index(row, column):
return (row - 1) * TABLE_SIZE + (column - 1)
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
for command in commands:
parts = command.split()
if parts[0] == "UPDATE":
# UPDATE r c value
if len(parts) == 4:
row = int(parts[1])
column = int(parts[2])
value = parts[3]
cell = to_index(row, column)
root = find(cell)
values[root] = value
# UPDATE value1 value2
else:
value1 = parts[1]
value2 = parts[2]
for cell in range(CELL_COUNT):
if (
parent[cell] == cell
and values[cell] == value1
):
values[cell] = value2
elif parts[0] == "MERGE":
row1 = int(parts[1])
column1 = int(parts[2])
row2 = int(parts[3])
column2 = int(parts[4])
cell1 = to_index(row1, column1)
cell2 = to_index(row2, column2)
root1 = find(cell1)
root2 = find(cell2)
# 이미 같은 병합 그룹이면 무시한다.
if root1 == root2:
continue
# 첫 번째 셀의 값이 우선한다.
merged_value = values[root1] or values[root2]
parent[root2] = root1
values[root1] = merged_value
values[root2] = ""
elif parts[0] == "UNMERGE":
row = int(parts[1])
column = int(parts[2])
target = to_index(row, column)
root = find(target)
saved_value = values[root]
# 부모 관계를 초기화하기 전에 그룹 구성원을 찾는다.
members = [
cell
for cell in range(CELL_COUNT)
if find(cell) == root
]
for cell in members:
parent[cell] = cell
values[cell] = ""
# 명령으로 선택한 셀만 기존 값을 유지한다.
values[target] = saved_value
elif parts[0] == "PRINT":
row = int(parts[1])
column = int(parts[2])
cell = to_index(row, column)
value = values[find(cell)]
answer.append(value if value else "EMPTY")
return answer코드 설명
표 크기
TABLE_SIZE = 50
CELL_COUNT = TABLE_SIZE * TABLE_SIZE표의 크기는 항상 50 × 50으로 고정되어 있으므로 전체 셀은 2500개다.
상수에 이름을 붙이면 좌표 변환과 반복문의 의미를 쉽게 파악할 수 있다.
값은 대표 셀에만 저장
values = [""] * CELL_COUNT병합된 모든 셀에 같은 값을 복사하지 않고 대표 셀 한 곳에만 값을 저장한다.
셀의 값을 읽거나 변경할 때는 항상 find를 통해 대표 셀을 먼저 찾는다.
root = find(cell)
values[root] = valueMERGE 값 우선순위
merged_value = values[root1] or values[root2]두 그룹이 모두 값을 가지고 있다면 첫 번째 위치인 (r1, c1)이 속한 그룹의 값을 사용해야 한다.
첫 번째 그룹의 값이 빈 문자열이면 두 번째 그룹의 값을 사용한다.
값을 결정한 뒤에 부모를 변경해야 기존 값을 잃어버리지 않는다.
UNMERGE 처리 순서
UNMERGE에서는 처리 순서가 중요하다.
기존 값 저장
병합 그룹의 모든 구성원 검색
모든 구성원의 부모와 값 초기화
선택한 셀에 기존 값 복원구성원을 찾기 전에 부모를 초기화하면 어떤 셀들이 같은 그룹이었는지 알 수 없게 된다.
따라서 반드시 구성원 목록을 먼저 만들어야 한다.
명령어 구분
두 UPDATE 명령은 첫 번째 단어가 같지만 전체 단어 개수가 다르다.
UPDATE r c value -> 단어 4개
UPDATE value1 value2 -> 단어 3개따라서 len(parts)로 두 명령을 구분할 수 있다.
간단한 예시
다음 명령을 순서대로 실행한다고 하자.
UPDATE 1 1 menu
MERGE 1 1 1 2
PRINT 1 2
UNMERGE 1 2
PRINT 1 1
PRINT 1 2(1, 1)에 "menu"를 저장하고 (1, 2)와 병합한다.
병합된 두 셀은 같은 값을 가지므로 첫 번째 출력은 다음과 같다.
menuUNMERGE 1 2를 실행하면 두 셀의 병합이 해제되고, 기존 값은 명령에서 선택한 (1, 2)에만 남는다.
따라서 이후 출력은 다음과 같다.
PRINT 1 1 -> EMPTY
PRINT 1 2 -> menu시간 복잡도
전체 셀의 수를 S, 명령어의 수를 C라고 하자.
S = 2500좌표 기반 UPDATE, MERGE, PRINT는 대표 셀 탐색을 제외하면 상수 시간에 처리된다.
UPDATE value1 value2와 UNMERGE는 전체 셀을 확인하므로 다음 시간이 필요하다.
O(S)모든 명령이 전체 셀 순회를 요구하는 최악의 경우 전체 시간 복잡도는 다음과 같다.
O(C × S)표의 크기가 50 × 50으로 고정되어 있어 충분히 처리할 수 있다.
공간 복잡도
각 셀의 부모와 값을 저장하는 배열을 사용한다.
O(S)UNMERGE에서는 같은 그룹에 속한 셀 목록도 최대 S개까지 저장한다.
정리
이 문제는 병합된 셀들을 하나의 집합으로 관리하는 Union-Find 구현 문제다.
풀이 흐름은 다음과 같다.
2차원 좌표를 1차원 번호로 변환
병합된 셀을 Union-Find 집합으로 관리
실제 값은 각 그룹의 대표 셀에만 저장
MERGE 시 첫 번째 셀의 값 우선
UNMERGE 시 기존 값을 보관한 뒤 그룹 초기화
선택한 셀에만 기존 값 복원특히 UNMERGE에서 병합 그룹의 구성원을 먼저 찾고, 명령으로 선택한 셀에 값을 복원하는 순서를 지키는 것이 핵심이다.
