글 읽기 - Python 시간초과의 늪에 빠졌습니다

black01676 1년 전 0

일반적인 merge sort를 구현해서 정렬할때마다 K번째인지 확인후 출력, 종료하도록

코딩하였습니다.

더 어디서 줄여야하는지 가르침부탁드립니다 ㅠㅠ

import sys
def cnt_check (ele) :
    global cnt, K
    cnt+=1
    flag = 0    #종료 flag
    if cnt==K :
        print (ele)
        flag = 1
    return flag

def merge (arr) :
    global cnt, K

    if len(arr) == 1:
        return arr
    if len(arr)%2 == 1 :
        mid = len(arr)//2+1
    else :
        mid = len(arr)//2
    pre = arr[:mid]
    post = arr[mid:]

    merge(pre)
    merge(post)

    i, j, k = 0, 0, 0
    while len(pre) > i and len(post) > j :
        if pre[i] <= post[j] :
            arr[k] = pre[i]
            i+=1
        else :
            arr[k] = post[j]
            j+=1
        if cnt_check(arr[k]) == 1:
            return
        k+=1

    while len(pre) > i :
        arr[k] = pre[i]
        if cnt_check(arr[k]) == 1:
            return
        i+=1
        k+=1

    while len(post) > j :
        arr[k] = post[j]
        if cnt_check(arr[k]) == 1:
            return
        j+=1
        k+=1

    return arr

A, K = map(int, sys.stdin.readline().split())
Arr = list(map(int, sys.stdin.readline().split()))
cnt = 0
if A == 1 :
    cnt = 1
    if cnt < K :
        print (-1)
    else :
        print (Arr[0])
else :
    merge(Arr)
    if cnt < K :
        print (-1)

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

문제

문제

출처

ICPC

Python 시간초과의 늪에 빠졌습니다

black01676 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말