백준 2357 최솟값과 최댓값(Gold1, Python)

Seop·2023년 8월 6일

알고리즘

목록 보기

12/16

최솟값과 최댓값

문제

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

정답 코드

Python

import sys

n, m = map(int, sys.stdin.readline().rstrip().split())
g = [int(sys.stdin.readline().rstrip()) for _ in range(n)]
min_tree = [0 for _ in range(len(g) * 4)]
max_tree = [0 for _ in range(len(g) * 4)]


def init_tree(start: int, end: int, node: int, tree: list, is_min: bool):
    if start == end:
        tree[node] = g[start]
        return tree[node]
    mid = (start + end) // 2
    if is_min:
        tree[node] = min(init_tree(start, mid, node * 2, tree, is_min),
                         init_tree(mid + 1, end, node * 2 + 1, tree, is_min))
    else:
        tree[node] = max(init_tree(start, mid, node * 2, tree, is_min),
                         init_tree(mid + 1, end, node * 2 + 1, tree, is_min))
    return tree[node]


def get_val(start: int, end: int, node: int, left: int, right: int, tree: list, is_min: bool):
    if left > end or right < start:
        return sys.maxsize if is_min else -sys.maxsize

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

    mid = (start + end) // 2
    if is_min:
        return min(get_val(start, mid, node * 2, left, right, tree, is_min),
                   get_val(mid + 1, end, node * 2 + 1, left, right, tree, is_min))
    else:
        return max(get_val(start, mid, node * 2, left, right, tree, is_min),
                   get_val(mid + 1, end, node * 2 + 1, left, right, tree, is_min))


init_tree(0, n - 1, 1, min_tree, True)
init_tree(0, n - 1, 1, max_tree, False)
for i in range(m):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    print(get_val(0, n - 1, 1, a - 1, b - 1, min_tree, True), get_val(0, n - 1, 1, a - 1, b - 1, max_tree, False))

해설

응용된 세그먼트 트리 문제입니다.
기존의 세그먼트 트리는 각 구간별로 합을 이용해 특정 구간 사이의 합을 구하거나, 특정 인덱스의 값을 변화시키되 O(log(n))의 시간복잡도로 구할 수 있도록 해주는 알고리즘 이라면
이 문제는 해당 개념을 그대로 들고와서 특정 구간의 최댓/솟값을 구하는데 사용할 겁니다!

def init_tree() : 인자로 들어오는 값을 기반으로 트리를 만들어 주는 함수입니다. 원래라면 tree[node] = init_tree() + init_treee() 이런식으로 합을 구하는데 사용하겠지만, 이 문제에서 요구하는 부분은 합이 아닌 최댓값과 최솟값을 구해주도록 min과 max 함수를 사용해줄겁니다. 그러면 재귀적으로 특정 구간에서의 최댓값과 최솟값을 구해주겠져!!
def get_val(): 트리를 구성하고 난 후, 해당 트리를 바탕으로 최솟값과 최댓값을 구해주는 함수입니다. 역시 달라진 곳은 합을 구하는 부분이 min, max 함수로 대체되었다는 점 뿐이요!

참고로 저는 최솟값과 최댓값을 구하는 함수를 한번에 처리하기 위해서 인자로 트리와 현재 구하는 값이 무엇인지 구분하는 flag(is_min)를 추가했습니다.

원래는 전역 영역에 존재하는 tree라는 리스트에 직접 접근을 했지만, 지금은 트리가 2개라서 인자로 받기로 한거죠!!