백준|2357번|최솟값과 최댓값

README·2023년 3월 23일
0

파이썬 PS풀이

목록 보기
132/136

문제 설명

n개의 숫자를 입력받고 그 숫자들 중 a번부터 b번까지의 수를 골라서 그중 가장 큰 수와 가장 작은 수를 출력하는 문제입니다.

작동 순서

  1. 숫자의 개수와 범위의 개수 N, M을 입력받습니다.
  2. 최솟값, 최댓값 세그먼트 트리를 각각 만들어줍니다. 세그먼트 트리는 구간별로 리스트를 분할하여 각 구간별 대푯값을 저장하는 트리입니다.
  3. 세그먼트 트리의 구간별 연산을 통해서 구간별 최솟값과 최댓값을 출력합니다.

소스코드

import sys


def makeMaxTree(tree, node, left, right):
    if left == right:
        tree[node] = num[left]
        return tree[node]

    mid = left + (right - left) // 2
    left_num = makeMaxTree(tree, 2 * node, left, mid)
    right_num = makeMaxTree(tree, 2 * node + 1, mid + 1, right)
    tree[node] = max(left_num, right_num)
    return tree[node]


def makeMinTree(tree, node, left, right):
    if left == right:
        tree[node] = num[left]
        return tree[node]

    mid = left + (right - left) // 2
    left_num = makeMinTree(tree, 2 * node, left, mid)
    right_num = makeMinTree(tree, 2 * node + 1, mid + 1, right)
    tree[node] = min(left_num, right_num)
    return tree[node]


def maxQuery(start, end, node, left, right):
    if end < left or start > right:
        return -1
    if start <= left and right <= end:
        return max_tree[node]
    mid = left+(right-left)//2
    left_num = maxQuery(start, end, 2*node, left, mid)
    right_num = maxQuery(start, end, 2*node+1, mid+1, right)
    return max(left_num, right_num)


def minQuery(start, end, node, left, right):
    if end < left or start > right:
        return 1e12
    if start <= left and right <= end:
        return min_tree[node]
    mid = left+(right-left)//2
    left_num = minQuery(start, end, 2*node, left, mid)
    right_num = minQuery(start, end, 2*node+1, mid+1, right)
    return min(left_num, right_num)


N, M = map(int, sys.stdin.readline().split())
num = []
for i in range(N):
    num.append(int(sys.stdin.readline()))
max_tree = [0 for _ in range(4*N)]
min_tree = [0 for _ in range(4*N)]
makeMaxTree(max_tree, 1, 0, N-1)
makeMinTree(min_tree, 1, 0, N-1)
for i in range(M):
    a, b = map(int, sys.stdin.readline().split())
    print(minQuery(a-1, b-1, 1, 0, N-1), maxQuery(a-1, b-1, 1, 0, N-1))
profile
INTP 개발자 지망생

0개의 댓글