ABC329 F번 복기 - 당연하지만 어려운 '작은 집합에서 큰 집합으로 합치는 테크닉(smaller to larger)' 배우기

1. 문제

 

다음과 같은 문제를 생각해보자.

 

크기가 1인 집합이 N개 있고 각 집합은 1부터 N까지 각각을 원소로 갖는 집합이다.

 

{1}, {2}, {3}, ... , {N}

 

이 집합을 합치는 연산을 반복하여 최종적으로 {1,2,3,...,N}이 되게 하고 싶다.

 

생각할 수 있는 방법은 {1}을 {2}에 넣어서 {1,2}로 만들고, {1,2}를 {3}에 넣어서 {1,2,3}으로 만들고..

 

{1,2,3}을 {4}에 넣어서 {1,2,3,4},...를 반복하면 {1,2,3,4,..,N}이 된다.

 

결국 i번 집합을 i+1번 집합에 넣는 과정을 N-1번 반복하면 되는 것이다.

 

--------------------------------------------------------------------------------------------------------------------------------------------------

 

그런데, 관점을 바꿔서 생각해보자.

 

위 과정은 {1,2}를 {3}에 넣어서 {1,2,3}으로 만들었지만...

 

사실 컴퓨터 프로그래밍 관점에서 생각해본다면... {1,2}를 {3}에 넣을 때는

 

{1,2}를 하나씩 순회해서 {3} >> {3,1} >>> {3,1,2}로 2번의 연산을 거치는데

 

반대로 {3}을 {1,2}에 넣는다면 어떨까?

 

그러면 {1,2,3}으로 단 1번의 연산으로 {1,2,3}이라는 같은 결과를 얻는다.

 

더욱 극단적인 예시로 {1,2,3,4,...,10000000}을 {10000001}이라는 집합과 합친다고 한다면...?

 

{1,2,3,4,...,10000000}을 {10000001}에 넣을려면 10000000번의 연산을 해야 {1,2,3,4,...,10000001}이 될 것이지만

 

{10000001}을 {1,2,3,4,...,10000000}에 넣으면 1번의 연산으로  {1,2,3,4,...,10000001}이 된다.

 

생각해보면 너무나도 당연하다.

 

두 집합을 합쳐서 하나의 집합으로 만들때, 컴퓨터 프로그래밍 관점에서 생각한다면 원소의 개수가 작은 집합에서

 

원소의 개수가 많은 집합으로 합치는 것이 무조건 유리하다.

 

이러한 테크닉을 작은 집합에서 큰 집합으로 합치는 테크닉(smaller to larger)이라고 부른다

 

 

2. 증명

 

크기가 p인 집합 A와 크기가 q인 집합 B가 있다고 할 때, p >= q라고 하자.

 

A와 B가 합쳐진다면 크기가 작은 집합에서 큰 집합으로 합친다고 할때, B의 원소를 A로 옮기게 된다.

 

그러면 p >= q에서 양변에 q를 더해주면 p+q >= 2q가 된다.

 

즉, 작은 집합에서 큰 집합으로 원소를 옮길 때마다 이동한 원소가 속하는 집합의 크기가 최소 2배이상 증가한다.

 

전체 원소의 수가 N개로 제한되어 있는데 2배 이상 증가하는 집합이 생기므로,

 

모든 원소는 최대 logN번 움직일 수 있고, 전체 시간복잡도는 O(NlogN)이 된다.

 

3을 기준으로 볼때,  최악의 경우 log8 = 3번 움직이는 경우는...

 

{1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}

 

{1,2} {3} {4} {5} {6} {7} {8}

 

{1,2} {3,4} {5} {6} {7} {8} (1번)

 

{1,2} {3,4} {5} {6,7} {8}

 

{1,2} {3,4,6,7} {5} {8} (2번)

 

{1,2,5,8} {3,4,6,7}

 

{1,2,3,4,5,6,7,8} (3번)

 

 

3. 연습문제

 

F - Colored Ball (atcoder.jp)

F - Colored Ball

 

 

4. 풀이

 

N개의 박스가 있는데 i번 박스에는 색 Ci인 공이 1개씩 들어있다.

 

q개의 쿼리를 처리하는데 박스 a의 모든 공을 b로 옮겼을때, 박스 b에서 서로 다른 색의 개수는 몇개인가

 

union find로 해야하냐... segment tree로 해야하냐.. F번이니까 어렵겠지 생각했는데..

 

의외로 생각보다 간단한 문제다

 

그냥 시키는대로 시뮬레이션 하면 된다

 

각 박스마다 서로 다른 색의 공을 가지고 있다는 것을 관리해야하니까 그것을 알 수 있도록 dictionary나 set으로 관리해줘야한다.

 

애초에 특정한 색의 공의 개수가 중요한건 아니고 각 박스가 서로 다른 색을 몇가지 가지고 있냐가 중요해서..

 

set으로 해도 될것 같기는 한디

 

나는 일단 dictionary로 해서 각 박스마다 초기에 어떤 색의 공을 가지는지 관리해두고..

 

매 쿼리마다 진짜 시키는대로 a에서 b로 옮기고 a를 빈 상자로 초기화한 다음... key의 길이를 print했는데

 

from sys import stdin

n,q = map(int,stdin.readline().split())

A = list(map(int,stdin.readline().split()))

box = {}

for i in range(1,n+1):
    
    box[i] = {A[i-1]:1}

for _ in range(q):
    
    a,b = map(int,stdin.readline().split())

    for key,value in box[a].items():
        
        if box[b].get(key,0) == 0:
            
            box[b][key] = value
        
        else:
            
            box[b][key] += value
    
    box[a] = {}

    print(len(box[b].keys()))

 

 

시간 초과 나더라고...

 

작은 개수를 가진 박스에서 다른 박스로 옮기는데는 그냥 옮겨도 상관 없지만...

 

10000개의 공을 가진 박스에서 3개의 공을 가진 다른 박스로 옮길때... 10000개나 옮겨야하잖아

 

억지로 만들면 색깔이 20만개 가능하니... 최악의 경우 20만*20만으로 당연히 시간초과날듯

 

애초에 이 생각 하긴 했는데.. 어떻게 해야하는지 몰랐지

 

근데 여기서 바로 "작은 집합에서 큰 집합으로 합치는 테크닉"이 필요하다 이거지

 

박스 a와 박스 b의 크기를 비교해서 a에서 b로 옮기는거지만 a의 크기가 b보다 크다면...

 

b에서 a로 옮기고 a라는 이름을 b로만 바꿔주면 끝이다.

 

두줄만 추가하면 0.5초정도 걸리더라

 

from sys import stdin

n,q = map(int,stdin.readline().split())

A = list(map(int,stdin.readline().split()))

box = {}

for i in range(1,n+1):

    box[i] = {A[i-1]:1}

for _ in range(q):

    a,b = map(int,stdin.readline().split())
    
    #작은 집합에서 큰 집합으로 합치는 테크닉
    #a에서 b로 옮기고 a를 빈 상자로 만들지만..
    #반대로 생각하면 b에서 a로 옮긴 다음 a라는 이름을 b로 바꿔주면, 
    #a에서 b로 옮기는거나 결과는 마찬가지다. 
    if len(box[a].items()) > len(box[b].items()):
        
        box[a],box[b] = box[b],box[a]

    for key,value in box[a].items():

        if box[b].get(key,0) == 0:

            box[b][key] = value

        else:

            box[b][key] += value

    box[a] = {}

    print(len(box[b].keys()))

 

 

각 공의 개수는 상관없으니까 set으로 관리해도 상관없을것 같아

 

0.4초 정도로 0.5초보다 조금 더 빠르긴함

 

from sys import stdin

n,q = map(int,stdin.readline().split())

A = list(map(int,stdin.readline().split()))

box = [0]*(n+1)

for i in range(1,n+1):

    box[i] = set([A[i-1]])

for _ in range(q):

    a,b = map(int,stdin.readline().split())

    if len(box[a]) > len(box[b]):
        
        box[a],box[b] = box[b],box[a]

    for c in box[a]:

        box[b].add(c)

    box[a] = set()

    print(len(box[b]))