[백준/BOJ] gold1 - 2357번 최솟값과 최댓값 (Python)

▶2357 - 최솟값과 최댓값

백준 로고

▶문제

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에 대한 답을 최솟값, 최댓값 순서로 출력한다.

728x90

▶풀이

보통 tree에는 값 하나만 넣어두는데, 이번에는 두 개를 넣었다.

최댓값과 최솟값을 한 번에 비교하기 위해서 그렇게 넣었다.

 

이번에는 update는 따로 없는 문제이고 init와 find만 만들어 주면 된다.

나머지는 다른 세그먼트 트리와 거의 똑같은 문제이다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

def init(start, end, index):
    if start == end:
        tree[index] = [arr[start], arr[start]]
        return tree[index]

    mid = (start + end) // 2
    l = init(start, mid, index * 2)
    r = init(mid + 1, end, index * 2 + 1)
    tree[index] = [min(l[0], r[0]), max(l[1], r[1])]

    return tree[index]


def find(start, end, index, left, right):
    if start > right or end < left:
        return [10 ** 9 + 1, 0]
    
    if left <= start and right >= end:
        return tree[index]
    
    mid = (start + end) // 2
    l = find(start, mid, index * 2, left, right)
    r = find(mid + 1, end, index * 2 + 1, left, right)
    return [min(l[0], r[0]), max(l[1], r[1])]
    
    
n, m = map(int, input().split())
arr = []
tree = [0 for _ in range(n * 4)]
answer = []

for _ in range(n):
    arr.append(int(input()))

init(0, n - 1, 1)

for _ in range(m):
    a, b = map(int, input().split())
    answer.append(find(0, n - 1, 1, a - 1, b - 1))

for ans in answer:
    print(*ans)