[python] 백준 2357 최솟값과 최댓값

www.acmicpc.net/problem/2357

2357번: 최솟값과 최댓값

 

이번에는 이 문제를 풀어볼게요.

 

세그먼트 트리를 이용해서 최솟값과 최댓값을 구하는 문제입니다.

 

이론파트에서 너무 누적합 얘기만 해서 찔렸거든요 헣헣

 

 

저번에 작성해뒀던 틀에서 조금의 수정으로 풀어보겠습니다. 

 

+ 연산 대신에 min 연산과 max 연산으로 고치면 되겠네요.

 

그러면 짜잔~

 

import math
import sys

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

N, M = map(int, input().split())

array = [0] * N

for i in range(N):
    array[i] = int(input())

h = int(math.ceil(math.log2(N)))
tree_size = (1 << (h + 1))
mintree = [0] * tree_size
maxtree = [0] * tree_size

def initmin(start, end, index):
    if start == end:
        mintree[index] = array[start]
        return mintree[index]
    mid = (start + end) // 2
    mintree[index] = min(initmin(start, mid, index * 2),initmin(mid + 1, end, index * 2 + 1))

    return mintree[index]

def querymin(start, end, index, left, right):
    if left > end or right < start:
        return math.inf
    if left <= start and end <= right:
        return mintree[index]
    mid = (start + end) // 2

    return min(querymin(start, mid, index * 2, left, right),querymin(mid + 1, end, index * 2 + 1, left, right))

def initmax(start, end, index):
    if start == end:
        maxtree[index] = array[start]
        return maxtree[index]
    mid = (start + end) // 2
    maxtree[index] = max(initmax(start, mid, index * 2),initmax(mid + 1, end, index * 2 + 1))
    return maxtree[index]

def querymax(start, end, index, left, right):
    if left > end or right < start:
        return -1
    if left <= start and end <= right:
        return maxtree[index]
    mid = (start + end) // 2

    return max(querymax(start, mid, index * 2, left, right),querymax(mid + 1, end, index * 2 + 1, left, right))

initmin(0, N - 1, 1)
initmax(0,N-1,1)

for i in range(M):
    s, e = map(int, input().split())
    print(querymin(0, N-1, 1, s-1, e-1),querymax(0,N-1,1,s-1,e-1))

 

이런 코드가 나온답니다.

 

제가 참.. 많이 틀렸던 부분이 있는데 querymin에서 범위 밖에 해당되는 경우에는 엄청 큰(입력으로는 주어지지 않는) 값을 리턴해줘야 합니다.

 

 

나름 백준에서 주어진 데이터 값 보고 따라 적었는데 0이 3개가 부족해서 자꾸 '틀렸습니다'가 떴었습니다.

 

더 이상 실수하지 않게 math에서 제공하는 inf를 종종 활용해야겠어요.

 

 

사실 지금 저 코드는 init과 query가 min,max별로 나뉘어져있습니다.

 

하나로 합치는 방법에 대해서 궁금하신 분들은 C++로 작성하신 블로거님의 링크를 달아둘테니 확인해주세요.

 

hddcp.tistory.com/31

[백준] 2357 - 최솟값과 최댓값