[백준2357번] 최솟값과 최댓값 / Python3

문제

N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.

여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다.

입력

첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가 주어진다. 다음 M개의 줄에는 a, b의 쌍이 주어진다.

출력

M개의 줄에 입력받은 순서대로 각 a, b에 대한 답을 최솟값, 최댓값 순서로 출력한다.

예제 입력 1

10 4
75
30
100
38
50
51
52
20
81
5
1 10
3 5
6 9
8 10

예제 출력 1

5 100
38 100
20 81
5 81

나의 풀이

이 문제는 10868번 최솟값문제와 아주 똑같다고 볼 수 있었다. 기존 최솟값 문제에서 비슷하게 최댓값을 담는 세그먼트 트리를 하나 더 만들고 최솟값과 최댓값을 초기화하는 함수 두개, 최솟값과 최댓값을 찾는 함수 두개를 만들면 됐다. 로직이 최솟값과 다른것도아니고 거의 min을 max로만 바꾸면 되었다.

필자는 이것을 파이썬으로 tree의 인자를 [최솟값,최댓값] 로 같이 저장하고 함수도 최솟값, 최댓값을 한번에 계산하는 함수를 만들어 init과 query함수를 한 개씩만 만들었었지만 시간초과가 나서 다시 쪼개니 문제를 해결할 수 있었다.

코드

# 2357번 최솟값과 최댓값
from math import *
import sys

# 세그먼트 트리 초기화
def initMin(node, start, end):
    if start == end:
        tree_min[node] = arr[start]
        return tree_min[node]

    mid = (start + end) // 2
    tree_min[node] = min(initMin(node*2, start, mid), initMin(node*2+1, mid+1, end))
    return tree_min[node]

def initMax(node, start, end):
    if start == end:
        tree_max[node] = arr[start]
        return tree_max[node]

    mid = (start + end) // 2
    tree_max[node] = max(initMax(node*2, start, mid), initMax(node*2+1, mid+1, end))
    return tree_max[node]

# 최솟값 쿼리
def queryMin(node, start, end, left, right):
    if start > right or end < left:
        return 1000000001

    if left <= start and end <= right:
        return tree_min[node]

    mid = (start + end) // 2
    return min(queryMin(node*2, start, mid, left, right), queryMin(node*2+1, mid+1, end, left, right))

# 최댓값 쿼리
def queryMax(node, start, end, left, right):
    if start > right or end < left:
        return 0

    if left <= start and end <= right:
        return tree_max[node]

    mid = (start + end) // 2
    return max(queryMax(node*2, start, mid, left, right), queryMax(node*2+1, mid+1, end, left, right))

# main
n, m = [int(x) for x in sys.stdin.readline().split()]

# 세그먼트 트리 사이즈 계산
h = int(ceil(log2(n)))       # 트리의 높이
t_size = 1 << (h+1)     # 대략의 트리 총 노드 개수

arr = []
tree_min = [0] * t_size     # 최솟값 저장
tree_max = [0] * t_size     # 최댓값 저장

for _ in range(n):
    arr.append(int(sys.stdin.readline()))

initMin(1,0,n-1)
initMax(1,0,n-1)

for _ in range(m):
    a, b = [int(x) for x in sys.stdin.readline().split()]

    print(queryMin(1, 0, n-1, a-1, b-1), end = ' ')
    print(queryMax(1, 0, n-1, a-1, b-1))