[백준] 13537 수열과 쿼리 1 - 머지소트트리(merge sort Tree) (Python)

문제링크

https://www.acmicpc.net/problem/13537

문제 총평

- 머지 소트 트리를 공부한다면 아주 쉽게 풀 수 있다.

문제 접근방식

- 이번 문제는 아무런 문제를 고른 것이 아닌 세그트리를 공부 후, 머지 소트 트리라는 것이 있어서 공부를 하고 나서 풀었습니다.

- 다른 요소가 중요하다기 보단 머지 소트 트리 연습 문제같은 느낌이니 머지 소트 트리를 모른다면 학습 후 문제를 푸시는 것을 추천드립니다.

- 또한 기존에는 sys를 잘 쓰진 않지만 이 문제에서는 sys로 입력을 받지 않으면 시간 초과가 뜨기 때문에 사용하였습니다.

정답코드

import bisect, math,sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int,input().split()))
size = math.ceil(math.log2(n))+1

tree = [[] for _ in range(1<<size)]

def merge(left,right):
    tem = []
    i = j = 0
    l = len(left)
    r = len(right)
    while 1:
        if i == l:
            for k in range(j,r):
                tem.append(right[k])
            break
        if j == r:
            for k in range(i,l):
                tem.append(left[k])
            break
        if left[i] < right[j]:
            tem.append(left[i])
            i += 1
        else:
            tem.append(right[j])
            j += 1
    return tem
def init(node,start,end):
    if start == end:
        tree[node].append(arr[start-1])
        return
    mid = start + end >> 1
    init(node<<1, start, mid)
    init(node<<1|1, mid+1, end)
    tree[node] = merge(tree[node<<1],tree[node<<1|1])

def query(node,s,e,l,r,k):
    if e<l or s>r: return 0
    if s >= l and e <= r:
        return len(tree[node]) - bisect.bisect_right(tree[node],k)
    mid = s + e >> 1
    return query(node<<1,s,mid,l,r,k) + query(node<<1|1,mid+1,e,l,r,k)
    

init(1,0,n)

for _ in range(int(input())):
    a,b,c = map(int,input().split())
    print(query(1,0,n,a,b,c))

1. 먼저 머지 소트 트리는 세그먼트 트리와 유사하게 만들어 집니다. 구간을 나눠서 값들을 저장합니다.
2. 그런데 세그먼트 트리와 다르게 어떤 노드가 특정 arr의 값이 아니라면 (start==end 가 아닌경우) 에는 그 하위 범위의 노드들을 머지 소트를 진행하여 만든 꼴이 됩니다.
3. 이는 merge 함수를 보면 되는데 이 함수는 다른 것이 아니라 여러분이 아는 머지 소트와 같은 코드입니다.
4. 이렇게 머지 소트를 이용해서 구간 안의 값들이 정렬 된 상태를 만들어 냅니다.
5. 그 이후에는 query 함수를 짜는데 특정 구간에서 k보다 큰 값을 찾기 위해서는 이분 탐색을 통해 k 보다 크면서 가장 작은 값의 index를 찾고 전체 길이에서 그 인섹스를 빼주면 됩니다.
6. 6 이 가능한 이유는 이미 머지 소트로 노드의 구간을 정렬해 놓았기 때문에 가능하고 직접 이분탐색을 할 수 있지만 저는 python의 bisect를 사용하였습니다.
7. 이렇게 구한 값을 더해 출력하면 됩니다. 

문제 풀이 후 생각

- 가장 먼저 든 생각은 알고리즘 세상에서는 참 자료구조가 많고 배울 것들이 많다는 것입니다.

- 개인적으로는 플레티넘 3 이라는 난이도는 자료구조가 어려워서 이겟지만 알고보면 참 쉬운 문제라는게 느껴집니다.

- 앞으로도 이런 새로운 자료 구조들을 소개 하고자 하니 많은 관심 부탁드립니다.

 

 

모르는게 있다면 댓글 남겨 주시면 바로 답해드리겟습니다 ^^