글 읽기 - [파이썬]시간차이

gyeongjj 3년 전 0

이분탐색을 사용안한 풀이와 사용한 풀이의 시간차이가 왜이렇게 많이 나는지 그리고 이분탐색을 사용한 풀이에서 시간이 많이 걸리는 부분이 어디인지 궁금합니다.

알려주시면 감사하겠습니다

#통과된 풀이(이분탐색사용x)
import sys
n = int(sys.stdin.readline().strip())
getNum = set(map(int,sys.stdin.readline().split()))
m = int(sys.stdin.readline().strip())
checkNum = list(map(int,sys.stdin.readline().split()))
for i in checkNum:
    if i in getNum:
        print(1)
    else:
        print(0)
#이분탐색이용(시간초과)
import sys
n = int(sys.stdin.readline().strip())
getNum = list(map(int,sys.stdin.readline().split()))
m = int(sys.stdin.readline().strip())
checkNum = list(map(int,sys.stdin.readline().split()))
getNum.sort()
for i in checkNum:
    count = 0
    first = 0
    last = n-1
    while count <= (n//2+1) or first <= last:
        middle = (first + last) // 2
        count +=1
        if i == getNum[middle]:
            print(1)
            break
        elif i > getNum[middle]:
            first=middle+1
        else:
            last=middle-1
    else:
        print(0)

shg9411 3년 전 1

이분탐색으로 통과됩니다.

채점번호 21250677

해쉬테이블로 이루어진 set을 사용하신 풀이는 숫자가 있는지 없는지 판별에 O(1)이 소요됩니다.

이분탐색은 O(logN)이고요.

아래 풀이의 경우는 출력 형식도 맞지 않네요.

gyeongjj 3년 전 0

알려주셔서 감사합니다.

덕분에 많이 알게 되었습니다.

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

문제

문제

출처

ICPC

[파이썬]시간차이

gyeongjj 3년 전 0

shg9411 3년 전 1

gyeongjj 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말