[백준/10868] 최솟값 (Python)

Problem : https://www.acmicpc.net/problem/10868

10868번: 최솟값

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:22:28

 

---

 

문제 설명

 

 

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에 대한 답을 출력한다.

 

입력 예시

 

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

 

출력 예시

 

5
38
20
5

 

 

---

 

풀이

 

세그먼트 트리 문제. 일반적으로 경우의 수를 따져 보면 O(NM)이 소요되므로 시간복잡도상 시간 초과가 날 게 뻔하다. lazy segment tree 문제도 이전에 풀이해봤었는데.. 왜 기억이 바로 안 났을까. 이전 문제들과도 거의 유사한 풀이를 적용할 수 있겠다. 이를테면 이것처럼.

 

2023.09.12 - [알고리즘 문제/백준] - [백준/1306] 달려라 홍준 (Python)

[백준/1306] 달려라 홍준 (Python)

2023.09.02 - [알고리즘 문제/백준] - [백준/11003] 최솟값 찾기 (Python)

[백준/11003] 최솟값 찾기 (Python)

 

세그먼트 트리의 경우 구간 최솟값을 구할 때 O(logN)의 시간복잡도가 소요되니, 총 시간복잡도는 O(MlogN)이 되어 쉽게 통과 가능하다.

 

 

풀이 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
nums = [int(input()) for _ in range(N)]
MAX = float('inf')
class SegTree :
  def __init__(self) :
    self.nodes = [0]*(4*N)
    self.init(1, N, 1)

  def init(self, start, end, idx) :
    if start == end :
      self.nodes[idx] = nums[start-1]
      return self.nodes[idx]
    mid = (start + end) // 2
    l = self.init(start, mid, idx*2)
    r = self.init(mid+1, end, idx*2+1)
    self.nodes[idx] = min(l, r)
    return self.nodes[idx]

  def cal(self, start, end, l, r, idx) :
    if r < start or end < l :
      return MAX
    if l <= start <= end <= r :
      return self.nodes[idx]
    mid = (start + end) // 2
    lval = self.cal(start, mid, l, r, idx*2)
    rval = self.cal(mid+1, end, l, r, idx*2+1)
    return min(lval, rval)

segtree = SegTree()
for _ in range(M) :
  a, b = map(int, input().split())
  print(segtree.cal(1, N, a, b, 1))

풀이 완료!