글 읽기 - 시간초과 설명 부탁드립니다.(python)

mksniper 1년 전 0

arrM의 요소를 이용하여 index함수로 arrN배열의 값 존재여부만 확인하였습니다.

O(n)으로 풀이가 되었다 생각하는데 더 효율적인 방법으로 진행해야 하는 걸까요?

import sys

N = int(sys.stdin.readline())
arrN = list(map(int, sys.stdin.readline().split()))

M = int(sys.stdin.readline())
arrM = list(map(int, sys.stdin.readline().split()))

for i in arrM:
    try:
        if arrN.index(i):
            print("1", end=' ')
    except ValueError:
            print("0", end=' ')

0000000000 1년 전 2

index() 함수의 시간복잡도가 O(N)이기 때문에 이 코드의 시간복잡도는 O(MN)이 됩니다.

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

문제

문제

출처

ICPC

시간초과 설명 부탁드립니다.(python)

mksniper 1년 전 0

0000000000 1년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말