[BOJ] 백준 2357번 문제 풀이 (Python)

1. 문제 풀이

구간별 최솟값과 최댓값을 구하는 문제이다. min, max함수는 모두 $O(N)$이 걸리기 때문에 사용하지 못했고 세그먼트 트리를 활용해서 문제를 풀었다.

세그먼트 트리(Segment Tree)

• 특정 구간에 대한 질문을 빠르게 대답하게 위해 쓰이는 꽉 찬 이진 트리 형태의 자료구조
  • 루트는 전체 구간의 정보를 담고 있다.
  • 왼쪽 자식 노드와 오른쪽 자식 노드는 부모 노드가 표현하는 구간의 왼쪽 절반에 대한 정보, 오른쪽 절반에 대한 정보를 포함한다.
• 구간을 절반씩 나눠서 정보를 포함하기 때문에 $O(logN)$안에 정해진 구간의 최솟값, 최댓값을 구할 수 있다.

2. 코드

• 코드를 작성할 때 최솟값과 최댓값을 나눠서 구하는 방식으로 작성했지만 한꺼번에 구하는 형태로도 작성할 수 있을 것 같다.

import sys
def input(): return sys.stdin.readline().rstrip()

class SegmentTree:
    def __init__(self,n,array):
        self.n = n
        self.array = array
        self.min_tree = [0] * (4*n)
        self.max_tree = [0] * (4*n)
        self.INT_MAX = int(1e15)
        self.INT_MIN = 0

        self.min_init(0,n-1,1)
        self.max_init(0,n-1,1)

    def min_init(self, left, right, idx):
        if left == right:
            self.min_tree[idx] = self.array[left]
            return self.min_tree[idx]
        mid = (left+right) // 2
        self.min_tree[idx] = min(self.min_init(left, mid, 2*idx),
                                 self.min_init(mid+1, right, 2*idx+1))
        return self.min_tree[idx]

    def max_init(self, left, right, idx):
        if left == right:
            self.max_tree[idx] = self.array[left]
            return self.max_tree[idx]
        mid = (left+right) // 2
        self.max_tree[idx] = max(self.max_init(left, mid, 2*idx),
                                 self.max_init(mid+1, right, 2*idx+1))
        return self.max_tree[idx]

    def min_query(self, left, right, idx, node_left, node_right):
        if node_left > right or node_right < left:
            return self.INT_MAX
        if left <= node_left and node_right <= right:
            return self.min_tree[idx]
        mid = (node_left+node_right) // 2
        return min(self.min_query(left, right, 2*idx, node_left, mid),
                   self.min_query(left, right, 2*idx+1, mid+1, node_right))

    def max_query(self, left, right, idx, node_left, node_right):
        if node_left > right or node_right < left:
            return self.INT_MIN
        if left <= node_left and node_right <= right:
            return self.max_tree[idx]
        mid = (node_left+node_right) // 2
        return max(self.max_query(left, right, 2*idx, node_left, mid),
                   self.max_query(left, right, 2*idx+1, mid+1, node_right))

    def find_min_max(self, left, right):
        return self.min_query(left, right, 1, 0, self.n-1), self.max_query(left,right, 1, 0, self.n-1)

n, m = map(int,input().split())
nums = [int(input()) for _ in range(n)]
segment_tree = SegmentTree(n, nums)
for _ in range(m):
    a, b = map(int, input().split())
    print(*segment_tree.find_min_max(a-1,b-1))