글 읽기 - 파이썬 시간초과 문제 도와주실수 있으십니까?

grapecw 3년 전 0

일단 생각나는건 대 해봤는데 시간 초과가 뜨네요.

문자열 비교는 오래 걸릴거 같아서 딕셔버리로 번호를 부여해서 탐색을 빠르게 했고,

안 바뀐것은 한번에 찾기 위해서 index로 찾고 있고,

한쪽으로 높이가 쏠리지 않기 위해 교환도 해줬는데 시간 초과가 나네요...

혹시 시간 복잡도를 개선하기 위한 더 좋은 방법이 있다면 알려 주실 수 있으십니까?

# https://www.acmicpc.net/problem/4195
import sys

input = sys.stdin.readline


def find(u):
    if (u == parent[u]):
        return u
    parent[u] = find(parent[u])
    return parent[u]


def merge(u, v):
    u = find(u)
    v = find(v)
    if (u == v):
        return
    if (level[u] > level[v]):
        u, v = v, u
    parent[u] = v
    if(level[u] == level[v]):
        level[v] = level[v] + 1


if __name__ == "__main__":
    T = int(input().strip())
    for _ in range(T):
        F = int(input().strip())
        peoplenum = 0
        # 문자열 비교 대신 정수로 비교하기 위한 정수형 배열
        parent = [i for i in range(2*F)]
        level = [1] * (2*F)
        # 빠른 위치 검색을 위한 딕셔너리
        names = {}
        for _ in range(F):
            # 입력받은 문자열을 찾는다.
            first, second = input().strip().split()
            # 딕셔너리에 없다면 이름을 추가하고 번호를 부여한다.
            if first not in names:
                names[first] = peoplenum
                peoplenum = peoplenum + 1
            if second not in names:
                names[second] = peoplenum
                peoplenum = peoplenum + 1
            # 각각 딕셔버리로부터 번호를 받아온다.
            first = names.get(first)
            second = names.get(second)
            temp1 = parent[first]
            temp2 = parent[second]
            # 두 이름을 union find
            merge(first, second)
            # 안 있다면 찾아서 바꿔준다.
            if temp1 != parent[first]:
                while temp1 in parent:
                    find(parent.index(temp1))
                cnt = parent.count(temp2)
            else:
                while temp2 in parent:
                    find(parent.index(temp2))
                cnt = parent.count(temp1)
            
            print(cnt)

grapecw 3년 전 0

딕셔너리는 해시맵 형식이니 O(n)까지는 안 가지 않나요....?

지식이 일천하다보니 지금까지 해시맵 형식인줄 알고 있었네요...

그리고 해봤는데 안되네요 ㅠㅠ

제가 어디 다른 곳을 잘못했나 봅니다 ㅠㅠ

더 나음 코드를 위한 조언에 감사드립니다

dietomorrow 3년 전 2

딕셔너리 해시맵형식이 맞고 평균 O(1), 최악(충돌이 많은 경우)의 경우 O(n)입니다.

54번째 코드부터 현재 merge하면서 할 수 있는 행위를 하는 코드같은데, 보통 다른 배열 하나를 만들어서 집합의 크기를 저장해주고 merge시에 변화시켜줍니다.

현재 코드에서는 count연산에서 O(n)이 소요되고, 관계가 100,000까지 들어올 수 있는데 매번 O(n)의 연산을 하기에 시간초과가 발생합니다.

grapecw 3년 전 0

감사합니다. 덕분에 해결했습니다.

count함수가 n만큼 시간이 소요 됬었군요.

더 나은 코드를 위한 조언에 감사드립니다.

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

문제

문제

출처

ICPC

파이썬 시간초과 문제 도와주실수 있으십니까?

grapecw 3년 전 0

grapecw 3년 전 0

dietomorrow 3년 전 2

grapecw 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말