글 읽기 - []와 {} 의 차이

cowgirl409 3년 전 0

아래 소스코드를 보면 제가 처음에 집합 S를 배열 형태로 받았는데 시간이 엄청 길게 나오더라구요.

근데 다른사람들 코드보면 {} 으로 집합으로 받는게 훨씬 빠르더라구요.

혹시 속도가 차이나는 이유를 알 수 있을까요?

import sys
input = sys.stdin.readline
#sys.setrecursionlimit(10000)

N,M = map(int,input().strip().split())

S = {input().strip() for i in range(N)}
#S = [input().strip() for i in range(N)]


count = 0
for i in range(M):
    if input().strip() in S:
        count += 1

print(count)

exqt 3년 전 1

배열에서 원소 x가 있는지 없는지 판별하는데 배열을 전체 다 둘러봅니다. 즉, 시간이 배열의 크기에 비례합니다.

반면, 파이썬 집합은 hash table을 이용하여 평균적으로 상수시간에 판별할 수 있습니다. (최악의 경우는 배열과 같지만 매우 드뭅니다)

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

문제

문제

출처

ICPC

[]와 {} 의 차이

cowgirl409 3년 전 0

exqt 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말