글 읽기 - 시간 초과인 이유가 무엇인가요?

hansatcode 1년 전 0

당연히 이분 탐색으로 구현하면 빠를 줄 알았으나, 오히려 단순하게 구현하는 것이 더 빠르군요.. (시행착오 끝에 쉬운 방법으로 정답을 받았긴 합니다.)

제가 이분 탐색 코드를 잘못 구성해서 그런 것인가요? 아니면 시간복잡도 개념에서 차이가 있어서 그런 것인가요? 문제 풀면서 궁금하여 질문 남겨봅니다 :)

import sys

for _ in range(int(sys.stdin.readline().strip('\n'))) :
    S1n = int(sys.stdin.readline().strip('\n'))
    S1 = set(map(int, sys.stdin.readline().strip('\n').split()))
    # S1 = sorted(set(map(int, sys.stdin.readline().strip('\n').split()))) # 중복 제거 <이분탐색>
    S2n = int(sys.stdin.readline().strip('\n'))
    S2 = list(map(int, sys.stdin.readline().strip('\n').split())) # 비교 대상
    
    for num in S2 :
        if num in S1 :
            print(1)
        else :
            print(0)

    # for S2_num in S2 :                       <이분 탐색>>
    #     left = 0
    #     right = len(S1) - 1
    #     while left <= right :
    #         mid = (right + left) // 2
            
    #         if S1[mid] == S2_num :
    #             sys.stdout.write(f'1\n')
    #             break
    #         elif S1[mid] > S2_num :
    #             right = mid - 1
    #         else : # S1[mid] < S2_num
    #             left = mid + 1
    #     else :
    #         sys.stdout.write(f'0\n')

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

문제

문제

출처

ICPC

시간 초과인 이유가 무엇인가요?

hansatcode 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말