글 읽기 - [Python 언어] 왜 시간 초과가 나오는지 모르겠습니다.

fourleaf 2년 전 0

왜 시간 초과가 나오는지 모르겠습니다. 답을 아시는 분이 계신다면 알려주시면 감사하겠습니다.

N=int(input(""))
A=list(map(int,input().split()))
M=int(input(""))
B=list(map(int,input().split()))

for j in range(M):
    if(B[j] in A):
        print("1")
    else:
        print("0")

wider93 2년 전 0

a가 리스트일 때, b in a는 a의 각 원소와 b를 비교하므로 최대 len(a)번의 비교를 하게 됩니다. 즉 이 코드는 7번 줄 만으로 최대 100000 * 100000 = 10^10번의 연산을 하게 되는 것인데 이는 감당할 수 있는 양이 아닙니다. 참고로 python보다 훨씬 빠른 c/c++에서 1초에 대략 10^9번의 연산을 감당합니다.

fourleaf 2년 전 0

그렇군요! 그러면 이 방법이 아닌 다른 방법을 찾아야 하는 건가요?

wider93 2년 전 0

네. 수학적으로 이야기하면 이 코드는 O(NM)의 시간복잡도를 가집니다. O(N+M)이나 O(NlogM) 등의 더 낮은 복잡도를 가진 방법이 필요합니다.

fourleaf 2년 전 0

네! 더 고민해보겠습니다. 감사합니다.

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

문제

문제

출처

ICPC

[Python 언어] 왜 시간 초과가 나오는지 모르겠습니다.

fourleaf 2년 전 0

wider93 2년 전 0

fourleaf 2년 전 0

wider93 2년 전 0

fourleaf 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말