[Python3] 2357 최솟값과 최댓값 - 골드 1

• 2022.02.14 포스팅 기준 solved.ac 문제 등급 : 골드 1
• 단계별로 풀어보기 -> 세그먼트 트리
• 알고리즘 분류
  • 자료구조
  • 세그먼트 트리

 

<링크>
https://www.acmicpc.net/problem/2357

2357번: 최솟값과 최댓값

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

 

---

<문제>
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에 대한 답을 최솟값, 최댓값 순서로 출력한다.

<예제 입력 1>

10 4
75
30
100
38
50
51
52
20
81
5
1 10
3 5
6 9
8 10

<예제 출력 1>

5 100
38 100
20 81
5 81

 

---

<풀이 접근>

이번 문제에서는 구간의 합 혹은 곱을 구하던 것 과는 달리, 구간의 최댓값과 최솟값을 구해야 합니다. 따라서, 리프노드를 제외한 각 서브트리의 노드에는 해당 서브트리 구간의 최댓값과 최솟값 쌍을 저장합니다.

이에 따라, 트리의 갱신 과정에서도 두 하위 서브트리의 최댓값과 최솟값을 반환 받고, 이들을 비교하여 노드의 값을 갱신합니다.

import sys
import math
input = sys.stdin.readline

n, m = map(int, input().split())
nums = [0]+[int(input()) for _ in range(n)]
pairs = [[*map(int, input().split())] for _ in range(m)]
seg_tree = [0 for _ in range((math.ceil(math.sqrt(n + 1))) ** 2 * 4 + 1)]


def make_tree(tree, start, end, v):
    if start == end:
        tree[v] = (nums[start], nums[start])
    else:
        mid = (start + end) // 2
        
        # 두 하위 서브트리 구간에서 각각의 최댓값과 최소값을 구하고, 그것들의 최대 최소를 구해 반환한다.
        m1, M1 = make_tree(tree, start, mid, v * 2)
        m2, M2 = make_tree(tree, mid + 1, end, v * 2 + 1)
        tree[v] = (min(m1, m2), max(M1, M2))
    return tree[v]


def find_minMax(tree, start, end, v, left, right):
    if end < left or right < start:
        return sys.maxsize, -1
    elif left <= start and end <= right:
        return tree[v]
    else:
        mid = (start + end) // 2
        
        # 마찬가지로 각각의 두 하위 구간에서 최대, 최소를 구해 반환한다.
        m1, M1 = find_minMax(tree, start, mid, v * 2, left, right)
        m2, M2 = find_minMax(tree, mid + 1, end, v * 2 + 1, left, right)
        return min(m1, m2), max(M1, M2)


make_tree(seg_tree, 1, n, 1)
res = ''

for a, b in pairs:
    m, M = find_minMax(seg_tree, 1, n, 1, a, b)
    res += str(m) + ' ' + str(M) + '\n'

print(res.rstrip())

 

위의 코드를 제출한 결과는 아래와 같습니다.

 

포스트 작성일 2022.02.17 기준 Python3 정답자 304명 중 55등 정도의 효율성입니다.
Python언어그룹 1등 풀이의 경우 Pypy3로 제출하여 160764KB 메모리, 312ms의 수행시간, 836B의 코드 길이를 보여줍니다.
Python3로 제출한 풀이 1등의 경우 36312KB 메모리, 976ms 수행시간, 1103B의 코드 길이를 보여줍니다.

---

<마무리>
구간의 합 부터 구간의 최댓값과 최솟값까지 기본적인 세그먼트 트리 문제를 다뤘습니다.
이 문제 풀이 역시 최적화의 여지가 남아있습니다.