글 읽기 - 파이썬으로 풀고 있는데 시간제한때문에 답답해서 올려봅니다.

blutics 6년 전 0

일단 아래 코드를 간략하게 설명드리면

merge의 경우 일단 전체 리스트를 병합정령하면서 세그트리를 만드는 과정에서 합쳐주는 용도로 만들었습니다.

그리고 mergeSort는 병합정렬을 하기 위해서 만들었고 하면서 segTree를 채워나갑니다.

여기서 sgTree는 u list에 저장됩니다.

그리고 변수 o에는 초기에 받아들이는 리스트가 저장됩니다.

다음으로 search함수는 만들어진 sgTree에서 query의 범위에 포함되는 정렬된 노드를 찾아서

그 노드의 인덱스를 저장하는 함수입니다. 저는 여기서 재귀적인 방법으로 구현했습니다.

그리고 이 인덱스를 리턴하는 방식이 아니라 함수호출시에 리스트를 주어서 거기에 담는 방식으로 구현했습니다.

마지막으로 mrange는 첫번째 인자로는 query 범위의 아랫부분 그리고 두번째 인자는 범위의 윗부분을 그리고 세번째는 index를 받고

search를 호출하여 sgTree의 노드를 찾고

그리고 그 노드들에서 이분탐색을 통해서 k번재 수를 찾는 일을 수행합니다.

여기서 k번째 수를 찾는 방법은 sgTree에서 찾은 노드들에서 하나씩 뽑아서

자신 보다 작은 원소가 몇개인지를 sgTree에서 찾은 노드들에서 몇개가 있는지를 확인을하고

만약 그 수가 원하는 인덱스와 같다면 그 수를 리턴하면서 종료하는 코드입니다.

그리고 보시면 원래 코드로 쓰이는 부분을 주석화하고 시간테스트하기 위해서 적어놓은게 있습니다.

그런데 이렇게 작성을 했는데 mrange가 단순히 query의 범위를 슬라이스해서 sorted시키고

거기서 인덱스로 조회하는것보다 훨씬 느리더라구요.

코드를 개판으로 작성해서 물어보는게 좀 죄송하기는 한데.....

그래도 한번은 물어보구 다시 짜보려구요ㅎ

==============================================================================================================

아 bsearch를 설명 안해놨네요.

bsearch는 리스트에서 주어지는 수보다 작은 수의 개수를 이분탐색으로 통해서 구하도록 작성하였습니다.

import math
import random
import time
def merge(a,b):
    x=0
    y=0
    c=[]
    if len(a)==0 or len(b)==0:
        if len(a)==0:
            return b
        else:
            return a
    while len(a)!=x and len(b)!=y:
        if a[x]<b[y]:
            c+=a[x],
            x+=1
        else:
            c+=b[y],
            y+=1
    if len(a)==x:c=c+b[y:]
    else:c=c+a[x:]
    return c
def mergeSort(x,y,w,z=1):
    t=len(x)
    if t==1:
        y[z]=[w[1],w[1],[*x]]
        return x
    k=t//2
    if len(x[:k])>=1:
        a=mergeSort(x[:k],y,[w[0],w[0]+k-1],z*2)
    if len(x[k:t])>=1:
        b=mergeSort(x[k:t],y,[w[0]+k,w[1]],z*2+1)
    c=merge(a,b)
    y[z]=[w[0],w[1],[*c]]
    return c
def search(t,y,z,l,x=1):
    a=t[x][0]
    b=t[x][1]
    if (a<=y<=b) or (a<=z<=b):
        if (a==y and b==y) or (a==z and b==z) or (a==y and b==z):
            l+=x,
            return
    else:
        if y<a and b<z:
            l+=x,
        return
    search(t,y,z,l,2*x)
    search(t,y,z,l,2*x+1)
def bsearch(a,b,w):
    k=(w[0]+w[1])//2
    if a[k]>b:
        if k<=0:
            return 0
        k=bsearch(a,b,[w[0],k])
    elif a[k]==b:
        return k
    else:
        if k+1>=len(a):
            return len(a)
        if a[k+1]>b:
            return k+1
        else:
            k=bsearch(a,b,[k+1,w[1]])
    return k
def mrange(x,y,z):
    l=[]
    search(u,x,y,l)
    for i in l:
        for j in u[i][2]:
            s=0
            for k in l:
                s+=bsearch(u[k][2],j,[0,len(u[k][2])-1])
            if s==z-1:
                return j

#a,b=map(int,input().split())
a,b=100000,100
u=[0]*2**(int(math.log(a,2))+2)
#o=[*map(int,input().split())]
o=list(set([random.randrange(200000) for i in range(100000)]))
mergeSort(o,u,[1,len(o)])
for i in range(b):
    #x,y,z=map(int,input().split())
    y=random.randrange(len(o))
    x=random.randrange(y)
    z=random.randrange(1,y-x)
    print('x : %d'%x)
    print('y : %d'%y)
    print('z : %d'%z)
    
    start=time.process_time()
    print('mrange = %s'%str(mrange(x,y,z)))
    end=time.process_time()
    print("랩타임 : %f초 입니다.\n"%(end-start))

    start=time.process_time()
    print('sorted = %s'%str(sorted(o[x-1:y])[z-1]))
    end=time.process_time()
    print("랩타임 : %f초 입니다."%(end-start))
    
    print('\n')

jh05013 6년 전 1

파이썬의 내장함수를 알면 구현할 필요 없이, 그리고 직접 구현하는 것보다 빠른 코드를 얻을 수 있습니다.

heapq.merge(L1, L2)는 L1, L2가 정렬되어 있다고 가정하고 이 둘을 정렬된 채로 합치는 generator를 만듭니다. 여기에 list를 씌우면 완성된 리스트를 얻습니다.

bisect 모듈에는 이분탐색 함수가 있습니다.

원하시는 함수와는 살짝 다를 수 있겠으나, 모든 변수명이 한 글자 알파벳이라서 알아보기 힘드네요.

blutics 6년 전 0

감사합니다. 올릴까 말까 고민하다가 한번 올리네요.

그리도 이런 조언이라도 받았으니 올리길 잘한것 같네요^^

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

문제

문제

출처

ICPC

파이썬으로 풀고 있는데 시간제한때문에 답답해서 올려봅니다.

blutics 6년 전 0

jh05013 6년 전 1

blutics 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말