[BOJ/python]14427번 수열과 쿼리 15

백준 14427번 수열과 쿼리 15 파이썬

문제 링크 - https://www.acmicpc.net/problem/14427

14427번: 수열과 쿼리 15

세그먼트 트리 문제를 공부해야겠다고 생각한 지 벌써 3개월은 된 것 같다. 심지어 이 문제도 트리를 이용한 해시 문제를 풀기 위해 시도했지만 도저히 안풀려서 알고리즘 분류를 보고 세그먼트 트리를 공부하게 되었다.

우선 쿼리 문제이기 때문에 python을 사용한다면 sys.stdin.readline을 이용하는 것이 정신건강에 도움이 된다.

트리에서 원하는 값을 인덱스로 얻기 위해 포화 이진 트리를 사용한다. leaf 노드에 주어진 값을 저장하고 값을 변경하라는 쿼리가 들어오면 leaf 노드의 값을 변경하고 루트 까지 bottom-up 방식으로 갱신해가면 된다. 값을 변경하기 위해 필요한 트리에서의 인덱스는 문제에서 주어지는 인덱스 + leaf 노드의 개수이다.

1. 풀이

• 포화 이진 트리를 만들기 위해 leaf 노드의 개수를 2**K의 형태로 만들어준다.
• leaf 노드에 문제에서 주어진 리스트의 값과 인덱스를 저장한다. (만약 주어진 값이 5개라면 leaf 노드의 개수는 8개이다. 이 때 트리의 총 노드의 개수는 15개이다.)
• leaf 노드의 부모 노드에서 루트까지 최솟값을 초기화한다.
• 최솟값의 인덱스를 출력하라는 쿼리가 들어오면 루트 노드에 저장된 인덱스를 출력한다.
• 값을 갱신하라는 쿼리가 들어오면 leaf 노드에서 해당하는 인덱스를 찾고 값을 변경한다.
• 해당 leaf 노드에서 루트 노드 까지 초기화했던 방식처럼 최솟값을 갱신해간다.

2. 코드

import math,sys
input = sys.stdin.readline
N = int(input())
L = list(map(int, input().split()))
M = int(input())

#leaf node의 개수 = 2**K의 형태로 맞춰주기
node = math.ceil(math.log2(N))
node = 2**node

#tree의 Node 개수 = 2*(node)
tree=[ [ float('inf'), -1 ] for _ in range(node*2) ]

#initialize (leaf)
for i in range(N):
    treeNum = i+node
    tree[treeNum] = [L[i], i]

#initailize (all node)
for i in range(node-1,0,-1):
    left, right = tree[2*i], tree[(2*i)+1]
    if left[0] <= right[0] :
        tree[i] = [left[0], left[1]]
    else:
        tree[i] = [right[0], right[1]]
        
def update(idx, value):
    treeNum = idx+node
    tree[treeNum][0] = value
    
    while treeNum!=1:
        treeNum = treeNum//2
        left, right = tree[2*treeNum], tree[(2*treeNum)+1]

        if left[0] <= right[0] :
            tree[treeNum] = [left[0], left[1]]
        else:
            tree[treeNum] = [right[0], right[1]]
        
#main
for _ in range(M):
    l = input().split()
    
    #루트 노드에 저장된 값 = [최솟값, 최솟값의 인덱스]
    if len(l)==1:
        print(tree[1][1]+1)
    
    else:
        _, i, v = l
        i,v = int(i), int(v)

        update(i-1, v)