[백준 2357] 최솟값과 최댓값- python (solved.ac - 골드 1)

https://www.acmicpc.net/problem/2357

2357번: 최솟값과 최댓값

풀이

문제를 보았을때 알수있는 힌트

세그먼트 트리 공부하면서 풀어본 문제입니다.

이 문제 역시 리스트에 연속적으로 존재하고 특정 범위의 최소,최대를 구하는 문제이기에 세그먼트 트리였습니다.

이전과 다르게 최소, 최대를 위해서 리스트에서 최소 최대를 마지막에 가지고 있게 작업하였습니다.

 

import sys

input = sys.stdin.readline

def init(start,end,node):
    if start==end:
        segment[node]=[n_list[start],n_list[start]]
        return segment[node]
    mid = (start+end)//2
    a= init(start,mid,node*2)
    b= init(mid+1,end,node*2+1)
    max_node = max(a[1],b[1])
    min_node = min(a[0],b[0])
    segment[node] = [min_node,max_node]
    return segment[node]

def query(start,end,node,left,right):
    if left>end or right < start:
        return [10**10,0]
    if left<=start and end<=right:
        return segment[node]
    mid = (start+end)//2
    a= query(start,mid,node*2,left,right)
    b= query(mid+1,end,node*2+1,left,right)
    # print(a,b)
    max_node = max(a[1],b[1])
    min_node = min(a[0],b[0])
    return [min_node,max_node]

n,m = map(int,input().split())
n_list = []
segment=[[0,0] for _ in range(4*n)]

for _ in range(n):
    temp = int(input())
    n_list.append(temp)
init(0,n-1,1)
for _ in range(m):
    b,c = map(int,input().split())
    print(*query(0,n-1,1,b-1,c-1))

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon2357.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리