[백준 2357번] 파이썬 - 최솟값과 최댓값

백준 2357_최솟값과 최댓값

시간제한 2초, 메모리 제한 192MB

# 조건

• N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다.
• 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다.
• 이 문제를 해결해 보자.
• 여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다.
  • 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 찾아야 한다.
  • 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다.

입력

• 첫째 줄에 N, M이 주어진다.
• 다음 N개의 줄에는 N개의 정수가 주어진다.
• 다음 M개의 줄에는 a, b의 쌍이 주어진다.

출력

• M개의 줄에 입력받은 순서대로 각 a, b에 대한 답을 최솟값, 최댓값 순서로 출력한다.

# 접근 방법

• 문제에서 나오듯이 단순히 구간에서 min, max를 사용한다면 시간 초과가 발생한다.
  • 또 정렬을 하여 구할 수 없으므로 이진 탐색도 불가하다.
• 이진 탐색과 비슷하게 특정 구간의 결과값을 찾을 수 있는 세그먼트 트리를 이용하여 풀어주었다.
  • 세그먼트 트리 참고 - https://cheon2308.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%EB%A6%ACSegment-Tree
• 세그먼트 트리의 크기의 경우 2**(H+1) -1 이지만 1부터 시작하기 위하여 -1을 해주지 않는다.
• init 함수
  • 세그먼트 트리를 저장해줄 함이다.
  • now, left, right 세 개의 포인터를 사용하여 left == right가 되는 경우 세그먼트 트리에 값을 저장해주면 된다.
  • 최대와 최소에 대해서 각각 실행해주면 된다.

# 세그먼트 트리 초기화  
def init_min(now, left, right):  
    if left == right:  
        tree_min[now] = nums[left]  
        return tree_min[now]  
    mid = (left + right) // 2  
    tree_min[now] = min(init_min(now*2, left, mid), init_min(now*2+1, mid+1, right))  
    return tree_min[now]  

def init_max(now, left, right):  
    if left == right:  
        tree_max[now] = nums[left]  
        return tree_max[now]  
    mid = (left + right) // 2  
    tree_max[now] = max(init_max(now*2, left, mid), init_max(now*2+1, mid+1, right))  
    return tree_max[now]  

N, M = map(int, input().split())  
nums = []  

# 세그먼트 트리 사이즈 계산하기  
H = int(ceil(log(N, 2)))  
seg_size = 1 << (H+1)  
tree_min = [0] * seg_size  
tree_max = [0] * seg_size  

for _ in range(N):  
    nums.append(int(input()))  

init_min(1, 0, N-1)  
init_max(1, 0, N-1)

• query 함수
  • 주어지는 쿼리 값에 따라 min과 max 값을 찾아주는 함수이다.
  • now, start, end, left, right를 인자로 받아준다.
    • left와 right는 현재 노드가 가지는 범위를 뜻하며
    • start와 end는 쿼리로 주어진 조건을 구하는 범위이다.
  • 구간이 노드의 값을 벗어나는 경우 최소의 경우 10억 1을 반환, 최댓값의 경우 0을 리턴해준다.
  • 구간을 완전히 포함한다면 트리 좌표의 값을 리턴해준다.
  • 노드의 구간이 요청 구간을 완전 포함하거나, 걸친다면 계속해서 재귀 탐색을 해주면 된다.

def query_min(now, start, end, left, right):  
    if start > right or end < left:  
        return 1000000001  
    if left <= start and end <= right:  
        return tree_min[now]  
    mid = (start+end) // 2  
    return min(query_min(now*2, start, mid, left, right), query_min(now*2+1, mid+1, end, left, right))  

def query_max(now, start, end, left, right):  
    if start > right or end < left:  
        return 0  
    if left <= start and end <= right:  
        return tree_max[now]  
    mid = (start+end) // 2  
    return max(query_max(now*2, start, mid, left, right), query_max(now*2+1, mid+1, end, left, right))

전체 코드

• 다음엔 bottom-up 방식을 이용해서 구현해볼 예정이다.

import sys  
from math import *  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

# 세그먼트 트리 초기화  
def init_min(now, left, right):  
    if left == right:  
        tree_min[now] = nums[left]  
        return tree_min[now]  
    mid = (left + right) // 2  
    tree_min[now] = min(init_min(now*2, left, mid), init_min(now*2+1, mid+1, right))  
    return tree_min[now]  

def init_max(now, left, right):  
    if left == right:  
        tree_max[now] = nums[left]  
        return tree_max[now]  
    mid = (left + right) // 2  
    tree_max[now] = max(init_max(now*2, left, mid), init_max(now*2+1, mid+1, right))  
    return tree_max[now]  

def query_min(now, start, end, left, right):  
    if start > right or end < left:  
        return 1000000001  
    if left <= start and end <= right:  
        return tree_min[now]  
    mid = (start+end) // 2  
    return min(query_min(now*2, start, mid, left, right), query_min(now*2+1, mid+1, end, left, right))  

def query_max(now, start, end, left, right):  
    if start > right or end < left:  
        return 0  
    if left <= start and end <= right:  
        return tree_max[now]  
    mid = (start+end) // 2  
    return max(query_max(now*2, start, mid, left, right), query_max(now*2+1, mid+1, end, left, right))  


N, M = map(int, input().split())  
nums = []  

# 세그먼트 트리 사이즈 계산하기  
H = int(ceil(log(N, 2)))  
seg_size = 1 << (H+1)  
tree_min = [0] * seg_size  
tree_max = [0] * seg_size  

for _ in range(N):  
    nums.append(int(input()))  

init_min(1, 0, N-1)  
init_max(1, 0, N-1)  


for _ in range(M):  
    a, b = map(int, input().split())  
    print(query_min(1, 0, N-1, a-1, b-1), query_max(1, 0, N-1, a-1, b-1))

• bottom-up 방식의 다른 분 코드
• 나의 코드와 시간차이가 3배가량 난다..

import sys
r = lambda: sys.stdin.readline()
input = sys.stdin.readline
N, M = map(int, input().split())
max_tree = [0] * (N*2)
min_tree = [0] * (N*2)

# Build maximum segment tree
def build_max_tree(N):
    for i in range(N-1, 0, -1):
        max_tree[i] = max(max_tree[i*2], max_tree[i*2+1])

# Build minimum segment tree
def build_min_tree(N):
    for i in range(N-1, 0, -1):
        min_tree[i] = min(min_tree[i*2], min_tree[i*2+1])

# Perform range maximum query
def max_query(left, right):
    left += N
    right += N
    max_val = 0
    while left <= right:
        if left % 2 == 1:
            max_val = max(max_val, max_tree[left])
            left += 1
        if right % 2 == 0:
            max_val = max(max_val, max_tree[right])
            right -= 1
        left //= 2
        right //= 2
    return max_val

# Perform range minimum query
def min_query(left, right):
    left += N
    right += N
    min_val = 10000000000
    while left <= right:
        if left % 2 == 1:
            min_val = min(min_val, min_tree[left])
            left += 1
        if right % 2 == 0:
            min_val = min(min_val, min_tree[right])
            right -= 1
        left //= 2
        right //= 2
    return min_val

for i in range(N):
    xxx = int(input())
    max_tree[N+i] = xxx
    min_tree[N+i] = xxx
build_max_tree(N)
build_min_tree(N)

for i in range(M):
    left, right = map(int, input().split())
    x = max_query(left-1, right-1)
    y = min_query(left-1, right-1)
    print(y, x)