[BOJ] 2357 - 최솟값과 최댓값 (Python)

 

 

아이디어

 

세그먼트 트리로 특정 범위에서의 최솟값과 최댓값을 저장해두고 찾는 범위에 대해 빠르게 처리한다.

 

 

풀이

 

N보다 큰 2의 거듭제곱 중 가장 작은 값의 두 배 크기로 0으로 채워진 리스트 min_tree를 만든다.

min_tree의 리프 노드들에 N개의 수를 입력 받고, min_tree를 복제하여 max_tree로 저장한다.

 

for문에서 min_tree와 max_tree의 부모 노드들을 각각 두 자식 노드 중 더 작은 값과 더 큰 값으로 저장해 나간다.

min_tree에서 값이 0인 자식 노드가 포함되어 있는 경우 부모 노드에 0이 아닌 자식 노드의 값을 저장한다.

M개의 a, b 쌍을 입력 받아 함수 find를 호출하여 반환된 최솟값과 최댓값을 언패킹하여 출력한다.

 

함수 find에서는 리프 노드에서부터 차례로 부모 노드로 올라가며 최솟값은 min_val에, 최댓값은 max_val에 저장한다.

s%2 == 1 또는 e%2 == 0처럼 두 자식 노드 중 한 노드만 포함되어 있다면 그 값을 min_val, max_val과 비교하고,

더 작거나 큰 경우에 각각을 갱신한 후 인덱스를 이동해 해당 노드의 부모 노드로 올라가지 않도록 한다.

 

import sys

input = sys.stdin.readline

def find(s, e):
    min_val, max_val = min_tree[s], max_tree[s]
    while s <= e:
        if s%2:
            if min_tree[s] < min_val:
                min_val = min_tree[s]
            if max_tree[s] > max_val:
                max_val = max_tree[s]
            s += 1
        if e%2 == 0:
            if min_tree[e] < min_val:
                min_val = min_tree[e]
            if max_tree[e] > max_val:
                max_val = max_tree[e]
            e -= 1
        s, e = s//2, e//2
    return min_val, max_val

N, M = map(int, input().split())
n = 1
while n < N:
    n *= 2
min_tree = [0]*(n*2)
min_tree[n:N+n] = [int(input()) for _ in range(N)]
max_tree = min_tree[:]
for i in range(n-1, 0, -1):
    if min_tree[i*2] and min_tree[i*2+1]:
        min_tree[i] = min(min_tree[i*2], min_tree[i*2+1])
    else:
        min_tree[i] = max(min_tree[i*2], min_tree[i*2+1])
    max_tree[i] = max(max_tree[i*2], max_tree[i*2+1])
for i in range(M):
    a, b = map(int, input().split())
    print(*find(a+n-1, b+n-1))