글 읽기 - [Python] 출력초과 코드와 정답 코드의 차이를 모르겠습니다

ebbunnim 3년 전 0

출력초과 코드에는, union하는 기준점을 문자열 순서 중 작은 것을 기준으로 하도록 했습니다.

정답 코드에는 쿼리로 들어오는 두 문자 중 왼쪽 문자만을 기준으로 union 하도록 했습니다.

보통 union-find에서 노드 번호가 작은 것을 기준으로 합쳐서 비슷하게 구현했는데 출력초과가 나는 이유는 무엇일까요?

import sys
from collections import defaultdict
input=sys.stdin.readline

# 출력초과 코드
def find_parent(x):
    if parent_dict[x]!=x:
        parent_dict[x]=find_parent(parent_dict[x])
    return parent_dict[x]

def union_parent(a,b):
    a=find_parent(a)
    b=find_parent(b)
    if a < b:
        parent_dict[b]=a
        cnt_parent[a]+=cnt_parent[b]
    else:
        parent_dict[a]=b
        cnt_parent[b]+=cnt_parent[a]

if __name__ == '__main__':
    T=int(input())
    for _ in range(T):
        F=int(input())
        parent_dict = defaultdict(str)
        cnt_parent=defaultdict(lambda:1)
        for _ in range(F):
            n1,n2=input().strip().split()
            if parent_dict[n1]=='':
                parent_dict[n1]=n1
            if parent_dict[n2]=='':
                parent_dict[n2]=n2
            union_parent(n1,n2)
            print(cnt_parent[find_parent(n1 if n1<n2 else n2)])
            
            
# 정답코드
def find_parent(x):
    if parent_dict[x]!=x:
        parent_dict[x]=find_parent(parent_dict[x])
    return parent_dict[x]

def union_parent(a,b):
    a=find_parent(a)
    b=find_parent(b)
    if a != b:
        parent_dict[b]=a
        cnt_parent[a]+=cnt_parent[b]

if __name__ == '__main__':
    T=int(input())
    for _ in range(T):
        F=int(input())
        parent_dict = defaultdict(str)
        cnt_parent=defaultdict(lambda:1)
        for _ in range(F):
            n1,n2=input().strip().split()
            if parent_dict[n1]=='':
                parent_dict[n1]=n1
            if parent_dict[n2]=='':
                parent_dict[n2]=n2
            union_parent(n1,n2)
            print(cnt_parent[find_parent(n1)])

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[Python] 출력초과 코드와 정답 코드의 차이를 모르겠습니다

ebbunnim 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말