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

josik97 3년 전 0

혼자 풀어보았는데 왜 시간초과가 나오는지 모르겠습니다..

N = int(input())
N_list = sorted(list(map(int, input().split())))
# 이진탐색 알고리즘을 사용하기 위해서 sorted 를 해주었다.

M = int(input())
M_list = list(map(int, input().split())) # 여기 있는 값이 N_list 안에 있는지 확인하면 된다.
 
for i in M_list:
    mid_index = int(len(N_list) / 2) # 2가 나오므로 중앙이다. 
    
    while True :
        if mid_index == -1 or mid_index == len(N_list) :
            print(0)
            break
        elif N_list[mid_index] == i :
            print(1)
            break 
        elif N_list[mid_index] > i :
            mid_index -= 1 
        elif N_list[mid_index] < i :
            mid_index += 1 

djm03178 3년 전 1

다음과 같은 입력에서 무한루프를 돌게 됩니다.

그리고 이 코드는 이분 탐색을 수행한 것이 아니라, 처음 탐색을 시작한 지점을 중앙으로 잡은 것뿐입니다. 이분 탐색을 하려면 mid를 한 칸씩 옮기는 것이 아니라 lo와 hi를 조정해서 계속해서 범위를 반으로 좁혀나가야 합니다.

josik97 3년 전 0

아 감사합니다!

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

문제

문제

출처

ICPC

왜 시간초과가 나오는지 모르겠습니다..

josik97 3년 전 0

djm03178 3년 전 1

josik97 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말