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

import sys
input = sys.stdin.readline

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

data = [0]*N
for i in range(N):
  data[i] = int(input())

maxsegtree = {}
minsegtree = {}
def makemaxseg(start,end,x):
  if start == end:
    maxsegtree[x] = data[start]
    return maxsegtree[x]
  else:
    mid = (start+end)//2
    maxsegtree[x] = max(makemaxseg(start,mid,x*2),makemaxseg(mid+1,end,x*2+1))
  return maxsegtree[x]

def makeminseg(start,end,x):
  if start == end:
    minsegtree[x] = data[start]
    return minsegtree[x]
  else:
    mid = (start+end)//2
    minsegtree[x] = min(makeminseg(start,mid,x*2),makeminseg(mid+1,end,x*2+1))
  return minsegtree[x]

def maxseg(n1,n2,start,end,x):
  if n1 == start and n2 == end:
    return maxsegtree[x]
  mid = (start+end)//2
  if n2 <= mid:
    return maxseg(n1,n2,start,mid,x*2)
  if n1 > mid:
    return maxseg(n1,n2,mid+1,end,x*2+1)
  return max(maxseg(n1,mid,start,mid,x*2),maxseg(mid+1,n2,mid+1,end,x*2+1))

def minseg(n1,n2,start,end,x):
  if n1 == start and n2 == end:
    return minsegtree[x]
  mid = (start+end)//2
  if n2 <= mid:
    return minseg(n1,n2,start,mid,x*2)
  if n1 > mid:
    return minseg(n1,n2,mid+1,end,x*2+1)
  return min(minseg(n1,mid,start,mid,x*2),minseg(mid+1,n2,mid+1,end,x*2+1))

makemaxseg(0,N-1,1)
makeminseg(0,N-1,1)

for i in range(M):
  a,b = map(int,input().split())
  print(minseg(a-1,b-1,0,N-1,1),maxseg(a-1,b-1,0,N-1,1))

 

세그먼트 트리로 구현하였다.

세그먼트 트리에서 합을 return하는것을 max 혹은 min을 return하도록 바꿔주면 된다.

 

나는 그냥 무식하게 max에 대한 세그먼트 트리와 min에 대한 segmant 트리를 둘다 만들어서 풀었는데, 다른 사람들 풀이를 보니 tuple로 min값과 max값을 둘다 저장하는 방법도 있다는 사실을 알게되었다.

 

 

오늘의 교훈) 알고리즘을 최대한 간략화하자