글 읽기 - [Python] 런타임 에러 질문입니다.

flame623 3년 전 0

16%에서 런타임에러에 걸리는데 어떤 부분이 문제일까요?

데이터 개수 작은 경우에서 해봤을땐 잘 찾는거 같았는데 원인을 모르겠습니다.

import sys

n = int(input())
L = sorted([sys.stdin.readline() for i in range(n)])

def find(n, L):
    l = len(L)
    if n == L[l//2]:
        return 1
    if l == 1:
        return 0
    if n < L[l//2]:
        return find(n, L[:l//2])
    else:
        return find(n, L[l//2:])

n2 = int(input())
for i in range(n2):
    print(find(sys.stdin.readline(), L))

shg9411 3년 전 1

1. 4,19번 라인 때문에 예제조차 돌아가지 않습니다.

2. 3과 11을 비교하면 11이 크지만 '3'과 '11'을 비교하면 '3'이 큽니다.

flame623 3년 전 0

주피터 환경에서 테스트를 해서 4번 19번 라인이 잘못된줄도 모르고 있었네요. 덕분에 런타임 에러는 확실히 잡았습니다. 감사합니다.

그런데 이제는 find 함수가 동작하는 부분에 자꾸 시간 초과가 발생하는데, 이거는 이유가 왜일까요? 마찬가지로 테스트할때는 제대로 잘 나오는것 같습니다.

import sys

def find(n, L):
    l = len(L)
    if n == L[l//2]:
        return "1"
    if l == 1:
        return "0"
    if n < L[l//2]:
        return find(n, L[:l//2])
    else:
        return find(n, L[l//2:])

n = int(input())
L = sorted(list(map(int, sys.stdin.readline().split())))

n2 = int(input())
for i in map(int, sys.stdin.readline().split()):
    sys.stdout.write("%s\n"%find(i, L))

djm03178 3년 전 1

L[:l//2]나 L[l//2:]가 해당 범위의 원소들을 전부 복사해서 새로운 리스트를 만들기 때문에 전체 탐색 과정에서 총 O(길이)개의 원소를 복사하게 되어 이분 탐색의 장점을 살릴 수가 없습니다. 리스트는 그대로 두고 인덱스를 통해서만 범위를 좁혀가야 합니다.

flame623 3년 전 0

감사합니다 덕분에 해결했습니다! 리스트 슬라이싱이 새롭게 복사해서 만든다는 사실을 몰랐었네요

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

문제

문제

출처

ICPC

[Python] 런타임 에러 질문입니다.

flame623 3년 전 0

shg9411 3년 전 1

flame623 3년 전 0

djm03178 3년 전 1

flame623 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말