글 읽기 - 파이썬 이분탐색 ㅜㅜ,,,,,

python0326 3년 전 0

런타임에러가 나요 테스트케이스는 잘 출력되는데 어느 부분에서 문제가 되는걸 까요,,??

n, c = map(int, input().split())
loc = []
for i in range(n):
    loc.append(int(input()))
loc.sort()


vis = [0] * (loc[-1]+1)
vis[loc[0]], vis[loc[-1]] = 1, 1
c -= 2
distance = []

def find():
    for i in range(len(loc)):
        if not vis[loc[i]]: #방문안한거 찾음
            # 왼쪽이랑 오른쪽 비교
            left, right = 0, 0
            for j in range(loc[i]-1, 0, -1):
                if vis[j]:
                    left = j
                    break
            for j in range(loc[i]+1, len(vis)):
                if vis[j]:
                    right = j
                    break
            distance.append( ( min(loc[i]-left, right-loc[i]) , loc[i] )  )

    distance.sort(key = lambda x : -x[0])
    return distance[0][1], distance[0][0]

if c == 0 :
    print(loc[1] - loc[0])
else :
    while c != 0 :
        distance = []
        node, dis = find()
        vis[node] = 1
        c -= 1
    print(dis)

BaaaaaaaaaaarkingDog 3년 전 0

일단 loc[-1]이 최대 10억인데 8번 줄에서 최대 10억이라는 크기의 배열을 잡기 때문에 런타임 에러가 발생하는 것으로 보입니다.

그런데 그 부분은 빼고서라도 알고리즘이 틀린 것으로 보입니다. 조금 조심스럽지만 python0326님이 푸신 문제 목록을 참고할 때 이 문제는 아마 아직 python0326님이 모르고계신 알고리즘을 쓰는 문제일 것으로 보입니다.

python0326 3년 전 0

아하ㅏㅏ 그렇군여 감사합니다 !-!

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

문제

문제

출처

ICPC

파이썬 이분탐색 ㅜㅜ,,,,,

python0326 3년 전 0

BaaaaaaaaaaarkingDog 3년 전 0

python0326 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말