글 읽기 - 시간초과 에러

oehdgns 1년 전 0

시간초과 에러가 어디서 나는지,에러 피드백 부탁드립니다ㅠㅠ

import sys

input = sys.stdin.readline

num1 = int(input())
card1 = list(map(int, input().split()))

num2 = int(input())
card2 = list(map(int, input().split()))


for i in card2:
    cnt = 0
    if i in card1:
        print(card1.count(i), end = " ")
    else:
        print(0, end = " ")

ufshg 1년 전 1

예시를 들어볼게요.

주어지는 카드배열 card1이 총 50만개고, 처음 499999개가 0, 마지막 카드가 1이라고 생각해보죠.

그리고 찾을 카드배열 card2도 50만개고, 전부 1이라고 생각하면

if i in card1 <= 이게 순차탐색이어서, 한번 찾는데 card1 안에 있는 50만개를 전부 순차로 탐색해나가서

결국 500000 * 500000 이라는 어마어마한 연산이 필요합니다.

간단하게 고쳐보려면 set()이나 dict로 선언 후 if i in card2 등을 사용해보세요.

이친구들은 in 연산 시간복잡도가 O(1)이랍니다.

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

문제

문제

출처

ICPC

시간초과 에러

oehdgns 1년 전 0

ufshg 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말