글 읽기 - 10815 파이썬 시간초과 질문입니다.

eunkyunghyun 3년 전 0

이 코드로 제출하였는데 왜 시간초과가 뜨는지 모르겠습니다...

m = int(input())
card_list = list(input().split())
n = int(input())
number_list = list(input().split())
string = ''
for number in range(len(number_list)):
    if number_list[number] in card_list:
        number_list[number] = 1
    else:
        number_list[number] = 0
    string += str(number_list[number]) + ' '
print(string)

djm03178 3년 전 0

in은 리스트 전체를 순회해야 하기 때문에 길이에 비례하는 시간이 걸립니다.

imn00133 3년 전 0

1) 6번은 card_list에서 in연산으로 찾는 것이기 때문에 O(n)이 걸린다고 볼 수 있습니다.

따라서 총 시간복잡도는 O(n^2)으로 예상됨으로, 시간초과가 납니다.

2) 답에 차이가 날 정도는 아니지만, string의 덧셈연산은 생각보다 느립니다.

' '.join과 stirng의 덧셈을 100000번 테스트 1회 해본 결과 2배정도 차이납니다.

(0.019/0.026)

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

문제

문제

출처

ICPC

10815 파이썬 시간초과 질문입니다.

eunkyunghyun 3년 전 0

djm03178 3년 전 0

imn00133 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말