글 읽기 - [파이썬] 시간초과 오류 질문입니다

h2j4607 2년 전 0

아래 실패코드로 진행 후 위 성공 코드를 작성하였습니다.

차이점은 아래 두곳을 명시해 두었는데요.

어디에서 문제가 발생한지 모르겠습니다.

제 생각엔 다른 점2에서 문제가 생겼을것으로 추측되는데요.

성공과 실패에 if문 차이가 1개 밖에 안나는데 이게 큰 문제로 작용할까요?

해당 부분의 문제가 맞을지, 그것에 대한 이유가 무엇인지 여쭙고 싶습니다.

## 성공 코드
import sys

N = int(sys.stdin.readline())
N_list = sorted((map(int, sys.stdin.readline().split())))

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

for target in M_list:
    start = 0
    end = N-1
    break_trigger = True

    while True:
        mid = (start + end)//2

        if N_list[mid] == target:
            print(1)
            break_trigger = False
            break
        elif N_list[mid] < target:
            start = mid+1
        elif N_list[mid] > target:
            end = mid-1
        if start>end:
            break

    if break_trigger:
        print(0)


## 실패(시간 초과) 코드
import sys

N = int(sys.stdin.readline())
N_list = sorted((map(int, sys.stdin.readline().split())))

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

for target in M_list:
    start = 0
    end = N-1
    mid = (start + end)//2
    
    # 성공 코드와 다른점 1 (line 48~52)
    if N == 1:
        if target == N_list[0]:
            print(1)
        else:
            print(0)

    while True:
        # 성공 코드와 다른점 2 (line 56~61)
        if start == end:
            if N_list[mid] == target:
                print(1)
            else:
                print(0)
            break

        if N_list[mid] == target:
            print(1)
            break
        elif N_list[mid] < target:
            start = mid+1
            mid = (start+end)//2
        elif N_list[mid] > target:
            end = mid-1
            mid = (start+end)//2

alsrjs0725 2년 전 1

이분탐색의 종료조건이 start == end일경우 몇몇경우 에서 무한으로 돌 수 있습니다 start > end의 경우를 종료조건으로 삼으시길 바랍니다

예를 들자면 arr = [1, 2, 3, 4, 5]에서 0을 찾으려 하는경우

아래부터 숫자는 인덱스입니다

시작은 0, 끝은 4이므로 중간은 2입니다 arr[2]는 3입니다 찾으려고 하는 값보다 크니 끝은 1이됩니다

시작은 0, 끝은 1이므로 중간은 0입니다 arr[0]은 1입니다 찾으려고 하는 값보다 크니 끝은 -1이 됩니다

시작은 0, 끝은 -1이므로 중간은 -1입니다 arr[-1]은 5입니다 찾으려고 하는 값보다 크니 끝은 -2가 됩니다

시작은 0, 끝은 -2이므로 중간은 -1입니다 arr[-1]은 5입니다 찾으려고 하는 값보다 크니 끝은 -2가 됩니다 (무한반복)

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

문제

문제

출처

ICPC

[파이썬] 시간초과 오류 질문입니다

h2j4607 2년 전 0

alsrjs0725 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말