글 읽기 - (파이썬)1920번 이진탐색법 시간초과가 왜 뜨는지 모르겠습니다 ㅠㅠ

zerohoney97 1년 전 0

기존에 있는 풀이 방식은 start,end를 써서 이진탐색을 하는 것이라면, 저는 배열을 잘라서 넣었습니다. 시간 복잡도는 logn으로 동일하지 않나요??

어느 부분에서 시간초과가 생기는지 알려주시면 감사드리겠습니다 ㅠㅠ

import sys
listNum = int(sys.stdin.readline())

listData = list(map(int, sys.stdin.readline().split()))


searchNum = int(sys.stdin.readline())
searchData = list(map(int, sys.stdin.readline().split()))

listData.sort()


def search(list, searchData):
    medium = len(list)//2
    if list[0] == searchData:
            return 1
    if len(list) == 1:
        if list[0] != searchData:
            return 0

    if list[medium] > searchData:
        return search(list[:medium], searchData)
    else:
        return search(list[medium:], searchData)


for index in searchData:
    print(search(listData, index))

ufshg 1년 전 1

시간복잡도 이외에,

리스트를 잘라서 전달하는 경우 함수 실행마다 아마도 리스트를 잘라서 새로운 리스트를 만들어 전달할겁니다.

이부분에서 시간이 많이쓰이지 않을까 싶네요.

pypy3로도 제출해보셨나요?

지금 봤는데, 이전 제 코드중 pypy3로 제출한 코드는 딱히 이분탐색 없이 그냥 if i in arr 로 처리했는데도 통과가 됐었네요.

zerohoney97 1년 전 0

역시 새 리스트 생성 때문에 그런건가요 ㅠㅠㅠ pypy3로도 동일하게 시간초과가 뜨네요 ㅎㅎㅎ 이분탐색 공부하고 처음 접한 알고리즘이라 풀고나서 스스로 엄청 자랑스러웠는데 ㅠㅠ 이렇게 틀리니까

슬픕니다 흑흑. 좋은 답변 감사드립니다!

djm03178 1년 전 1

슬라이싱을 쓰지 않으면 됩니다. 슬라이싱을 하면 결국 원소 전체를 다 복사하게 되어 이분 탐색을 하는 의미가 없어집니다.

zerohoney97 1년 전 0

이해 했습니다! ㅎㅎ 감사합니다!!!

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

문제

문제

출처

ICPC

(파이썬)1920번 이진탐색법 시간초과가 왜 뜨는지 모르겠습니다 ㅠㅠ

zerohoney97 1년 전 0

ufshg 1년 전 1

zerohoney97 1년 전 0

djm03178 1년 전 1

zerohoney97 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말