글 읽기 - [python 2] 왜 naive하게 구현한게 더 빠를까요?

ploffer11 5년 전 0

집합을 정말로 구현한것과, 집합에 수가 있는지 없는지 배열로 표현한 두개로 제출해서 둘다 맞았습니다.

그런데 집합을 정말 구현한게 더 시간이 짧습니다

왜그런지 궁금합니다.

#파이썬의 list형식을 이용한 코드
import sys
jiphap=[]
for x in xrange(input()):
    data=sys.stdin.readline().split()
    if len(data)==2:b=int(data[1])
    a=data[0]  
    if a=='add':
        if jiphap.count(b)==0:
            jiphap.append(b)
    elif a=='check':
        if jiphap.count(b)==1:
            print '1'
        else:
            print '0'
    elif a=='remove':
        try:
            jiphap.remove(b)
        except:pass
    elif a=='toggle':
        if jiphap.count(b)==1:
            jiphap.remove(b)
        else:
            jiphap.append(b)
    elif a=='all':
        jiphap=range(1,21)
    elif a=='empty':
        jiphap=[]
    
# 최적화 시킨(시켰다고 생각한) 코드
import sys
jiphap=[0]*21
for x in xrange(input()):
    data=sys.stdin.readline().split()
    if len(data)==2:b=int(data[1])
    a=data[0]  
    if a=='add':jiphap[b]=1
    elif a[0]=='c':
        print jiphap[b]
    elif a[0]=='r':
        jiphap[b]=0
    elif a[0]=='t':
        jiphap[b]=1-jiphap[b]
    elif a[0]=='a':
        for y in xrange(1,21):jiphap[y]=1
    elif a[0]=='e':
        for y in xrange(1,21):jiphap[y]=0
       

ploffer11 5년 전 0

다시 생각해보니 ALL이나 EMPTY가 복잡도를 차지해 오래 걸리는 것 같네요.

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

문제

문제

출처

ICPC

[python 2] 왜 naive하게 구현한게 더 빠를까요?

ploffer11 5년 전 0

ploffer11 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말