글 읽기 - 시간 초과문제

myharu01 1년 전 0

아래와 같은 코드에서 시간 초과가 발생하는데 이유를 알수있을까요??

# a,b = map(int,input().split())
import sys

sys.stdin.readline()
L = list(sys.stdin.readline().split())
sys.stdin.readline()
nL = list(map(lambda x: 1 if x in L else 0, sys.stdin.readline().split()))
for i in nL:
    print(i, end=' ')

junyub2 1년 전 2

두번째, 네번째에 받는 카드의 갯수가 최대일때

연산 횟수가 500,000 x 500,000 = 250,000,000,000 으로 해당 문제의 제한시간인 2초를 한참 뛰어넘는 계산시간이 걸립니다

초당 20,000,000 ~ 100,000,000 정도의 연산을 하는데 최소의 경우로 생각해서 코드를 작성하시는게 좋습니다.

10815 문제 같은 경우에는 이진탐색을 활용해서 코드를 다시 짜보시길 추천드립니다.

myharu01 1년 전 1

네 말씀해주신 대로 이진 탐색 알고리즘을 조금 수정하여 풀었습니다!

import sys

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        if array[mid] == target:
            return 1
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return 0

n = int(input())
card = list(map(int, sys.stdin.readline().split()))
m = int(input())
check = list(map(int, sys.stdin.readline().split()))

card.sort()


for i in range(m):
    print(binary_search(card, check[i], 0, n - 1), end=' ')

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

문제

문제

출처

ICPC

시간 초과문제

myharu01 1년 전 0

junyub2 1년 전 2

myharu01 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말