[백준]1849 순열 #세그먼트트리#파이썬

1. 풀이

(1) 숫자를 넣는 방법

숫자를 1부터 차례대로 적절한 위치에 집어넣는다.  숫자를 1부터 집어넣기 때문에 집어넣을 위치 앞에 아직 차지 않은 부분은 무조건 현재넣을 숫자보다 크고, 이미 차있는 숫자는 현재숫자보다 작다.

(2) 세그먼트 트리

따라서 숫자가 들어갈 위치를 세그먼트트리를 이용해서 찾는다. 세그먼트트리를 이용해서 구간합을 구해주는데, 이를 이용하여 현재 위치앞에 몇개의 숫자가 있는지를 빠르게 확인해준다.

 

* 처음에 update함수 따로, 위치를 찾는 함수를 따로 구현해서 시간 초과가 떳다(소스코드1). 위치를 찾으면서 바로 수정을 해야 통과한다.

2. 소스코드

(1) 소스코드1 (update함수, 쿼리함수 따로구현, 시간초과)

import sys
import math

def init(node,start,end):
    if start==end:
        tree[node]=1
        return 1

    mid=(start+end)//2
    tree[node]=init(node*2,start,mid)+init(node*2+1,mid+1,end)
    return tree[node]

def query(node,start,end,val):
    mid=(start+end)//2
    if start==end:
        return start
    if tree[node*2]>=val:
        return query(node*2,start,mid,val)
    return query(node*2+1,mid+1,end,val-tree[node*2])

def update(node,start,end,indx):
    if not start<=indx<=end:
        return

    tree[node] -= 1
    if start==end:
        return

    mid=(start+end)//2
    update(node*2,start,mid,indx)
    update(node*2+1,mid+1,end,indx)

N=int(input())
size=2**(math.ceil(math.log(N,2))+1)
tree=[0 for i in range(size)]
L=[0 for i in range(N+1)]
init(1,1,N)

for i in range(1,N+1):
    indx=query(1,1,N,int(sys.stdin.readline().rstrip())+1)
    L[indx]=i
    update(1,1,N,indx)

for i in range(1,N+1):
    print(L[i])

 

(2) 소스코드2 (통과)

import sys
import m

def init(node,start,end):
    if start==end:
        tree[node]=1
        return 1

    mid=(start+end)//2
    tree[node]=init(node*2,start,mid)+init(node*2+1,mid+1,end)
    return tree[node]

def query(node,start,end,val):
    tree[node]-=1

    if start==end:
        return start
    mid = (start + end) // 2
    if tree[node*2]>=val:
        return query(node*2,start,mid,val)
    return query(node*2+1,mid+1,end,val-tree[node*2])

def update(node,start,end,indx):
    if not start<=indx<=end:
        return

    tree[node] -= 1
    if start==end:
        return

    mid=(start+end)//2
    update(node*2,start,mid,indx)
    update(node*2+1,mid+1,end,indx)

N=int(input())
size=2**(math.ceil(math.log(N,2))+1)
tree=[0 for i in range(size)]
L=[0 for i in range(N+1)]
init(1,1,N)

for i in range(1,N+1):
    indx=query(1,1,N,int(sys.stdin.readline().rstrip())+1)
    L[indx]=i

for i in range(1,N+1):
    print(L[i])