글 읽기 - 파이썬3 시간초과 문제

debuglog 6년 전 0

quick selection으로 풀려고 하는데 잘안되네요 ㅠㅠ

피벗위치를 바꿔보기도 했는데 마찬가지입니다.

다른 접근방식이 있을까요?

import sys

def quick_selection(arr, kth, low, high):
    index = low
    for i in range(low, high):
        if arr[i] <= arr[high]:
            arr[index], arr[i] = arr[i], arr[index]
            index += 1
    arr[index], arr[high] = arr[high], arr[index]
    
    if index == kth:
        return arr[index]
    elif index < kth:
        return quick_selection(arr, kth, index+1, high)
    else:
        return quick_selection(arr, kth, low, index-1)

def median(arr):
    return quick_selection(arr, (len(arr)+1)//2-1, 0, len(arr)-1)
    
    
n, k = map(int, sys.stdin.readline().split(" "))
arr = []
for i in range(n):
    arr.append(int(sys.stdin.readline()))

sum = 0
for i in range(n-k+1):
    sum += median(arr[i:i+k])

sys.stdout.write(str(sum)+'\n')

jh05013 6년 전 0

모든 입력에 대해 시간 안에 돌아가야 하므로 최악의 경우도 고려해야 합니다.

피벗 위치를 랜덤으로 하면 돌아가려나요?

debuglog 6년 전 0

랜덤으로 바꾸고 돌려봤는데도 계속 시간초과가 뜨네요 ㅠ.ㅠ

jh05013 6년 전 1

입력의 크기 상으로 Quick selection으로는 안 될 것 같네요. N*K보다 빠르게 푸는 방법이 있습니다. (구간트리, 이진 탐색 트리 등) 솔직히 이게 9단계에 있을 만한 문제는 아닌 것 같습니다.

debuglog 6년 전 0

감사합니다! 나중에 다시 풀어봐야게네요ㅠ

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

문제

문제

출처

ICPC

파이썬3 시간초과 문제

debuglog 6년 전 0

jh05013 6년 전 0

debuglog 6년 전 0

jh05013 6년 전 1

debuglog 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말