[Python] 2357 - 최솟값과 최댓값 (골드1)

1. 문제 설명

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

2357번: 최솟값과 최댓값

 

---

2. 아이디어

숫자 100,000개 주고 구간(1, 100,000)을 100,000줬다고 생각해보자.

O(N) 알고리즘으로 구현해도 2초 안에 해결하기란 무리다.

그렇기 때문에 min(), max()함수를 사용하겠다는 얄팍한 생각으로는 이 문제를 찢을 수 없다.

 

시간복잡도 O(logN)를 가지는 알고리즘이 필요한데, log면 보통 트리다.

즉 이진 트리에 [min, max]값을 구간별로 저장해두면 해결할 수 있는 문제다.

 

구현이 힘들어서 그렇지 아이디어는 금방 떠올릴 수 있는 문제였다.

 

---

3. 코드

import sys

sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

n, m = map(int, input().split()) # 1 <= N <= 100,000, 1 <= M <= 100,000
sequence = []
for _ in range(n):
    sequence.append(int(input()))

def fill_seg(left, right, idx, arr):
    if left == right:
        arr[idx] = (sequence[left], sequence[right])
        return arr[idx]

    mid = (left + right) // 2

    left = fill_seg(left, mid, idx * 2 + 1, arr)
    right = fill_seg(mid + 1, right, idx * 2 + 2, arr)

    arr[idx] = (min(left[0], right[0]), max(left[1], right[1]))
    
    return arr[idx]


def search_tree(left, right, idx, a, b, arr):
    if a > right or b < left:
        return (1000000001, 0)

    if a <= left and right <= b:
        return arr[idx]

    mid = (left + right) // 2

    left = search_tree(left, mid, idx * 2 + 1, a, b, arr)
    right = search_tree(mid + 1, right, idx * 2 + 2, a, b, arr)

    return (min(left[0], right[0]), max(left[1], right[1]))
    

def solution():    
    size_node = 1
    while size_node < n:
        size_node <<= 1
    size_node <<= 1
    seg_tree = [0]*size_node

    fill_seg(0, n-1, 0, seg_tree)

    for _ in range(m):
        a, b = map(int, input().split())
        print(" ".join(map(str, search_tree(0, n-1, 0, a-1, b-1, seg_tree))))


solution()