[백준 1849번] 순열 (Python3)

import sys
input = sys.stdin.readline

def updatefenwick(i):
  if not i:
    return
  while i<=M:
    fenwick[i] += 1
    i += i&-i

def sumfenwick(i):
  SUM = 0
  while i:
    SUM += fenwick[i]
    i -= i&-i
  return SUM

def find(x,i,c):
  x1 = i-sumfenwick(i)
  if x>x1:
    return find(x,i+2**c,c-1)  
  if x<x1 or permutation[i-1]:
    return find(x,i-2**c,c-1)
  return i

N,M = int(input()),1<<17
permutation = [0]*N

fenwick = [0]*(M+1)
for i in range(1,N+1):
  idx = find(int(input())+1,M,16)
  permutation[idx-1] = i
  updatefenwick(idx)
print(*permutation,sep="\n")

팬윅트리 + 이분탐색으로 구현하였다.

사탕상자 [백준 2243번] 사탕상자 (Python3) (tistory.com) 와 비슷한 방법으로 해결할 수 있다. 다만 사탕상자와 비슷한 문제라는 사실을 떠올리기 까다로웠고, 구현도 까다로운 부분이 있었다.

 

아이디어를 설명하면,

1. 1부터 N까지 각 원소의 값을 입력받을 때, 현재의 숫자가 들어가야하는 위치는, 앞의 비어있는 노드의 개수가 입력값만큼 있는 곳이다. (비어있는 노드에는 현재의 숫자보다 더 큰 값만 들어갈 것이기 때문이다)

2. 위치에 숫자를 넣으면 그 뒤의 위치는 비어있는 노드의 개수가 1씩 줄어든다. 이를 팬윅트리로 구현한다.

3. 비어있는 노드의 개수 = 인덱스값 - 인덱스 앞에 채워져있는 숫자의 개수 = 입력값인 곳을 이분탐색으로 찾는다.

 

 

오늘의 교훈) 세그먼트 트리 + 이분탐색에 익숙해지자