[baekjoon] 11003 최솟값 찾기 (python)

[baekjoon] 11003 최솟값 찾기 (python)

11003 최솟값 찾기 Link

문제

길이가 L인 구간에서의 최솟값을 찾는 문제

문제 접근

세그먼트 트리

일단 처음에는 길이 L 구간에서의 최솟값을 빠르게 구하기 위해 세그먼트 트리 를 이용해서 구현해보았다.

수열 A에서 i번째 숫자를 트리에서 업데이트하는데 logN, 업데이트 후 구간에서의 최솟값을 가져오는데에 logN으로

O(NlogN) 의 시간복잡도를 가진다.

# input N, L = map(int, input().split()) arr = [0] arr.extend(list(map(int, input().split()))) MAXN = 5000000 tree = [0 for _ in range(MAXN * 2 + 1)] inf = 1000000000 def query(node, s, e, l, r): # node - 현재 노드 번호 # s, e - 현재 노드가 담당하는 구간 # l, r - 내가 원하는 구간 if r < s or e < l: return inf if l <= s and e <= r: return tree[node] mid = (s + e) // 2 return min(query(node * 2, s, mid, l, r), query(node * 2 + 1, mid + 1, e, l, r)) def update(node, s, e, idx, val): # node - 현재 노드 번호 # s, e - 현재 노드가 담당하는 구간 # idx - 값을 변경하려는 노드 번호 # val - 변경하려는 값 if idx < s or e < idx: return if s == e: tree[node] = val else: tree[node] = val if tree[node] == 0 else min(tree[node], val) mid = (s + e) // 2 update(node * 2, s, mid, idx, val) update(node * 2 + 1, mid + 1, e, idx, val) answer = [] for i in range(1, N + 1): update(1, 1, N, i, arr[i]) if i - L + 1 < 1: answer.append(query(1, 1, N, 1, i)) else : answer.append(query(1, 1, N, i - L + 1, i)) print(answer)

O(NlogN)이면 될 줄 알았으나...

시간이 생각보다 많이 빡빡하다 ㅠㅠ NlogN 으로 안되는 문제인가보다.

슬라이딩 윈도우

NlogN이 아니면 N 타임 안에 가능하다는 건데...라고 생각해보니 슬라이딩 윈도우 방식으로 하면 될 것 같았다.

슬라이딩 윈도우 방식으로 할 때의 문제점.

다음 구간으로 넘어갈 때 최솟값이 바뀌면 어떻게 찾지?

단순하게 구현하면 윈도우에서 최솟값이 빠질 때마다 윈도우를 탐색하면서 최솟값을 찾아야한다.

이렇게 되면 최악의 경우에는 O(N^2)이 될 수 있을 것.

어떻게 하면 구간에서 최솟값을 바로 찾을 수 있을까?

문제를 잘 생각해보면 같은 구간 내에서 j < i 이고 A(j) > A(i) 인 경우 A(j)는 절대로 구간의 최솟값이 될 수 없다.

이 점과 deque를 이용하면 마치 min-heap과 같은 효과를 낼 수 있다.

A(i)를 deque에 넣기 전, A(i)보다 작은 값들은 다 빼버리는 것.

이렇게 하면 deque의 맨 앞의 값이 구간에서의 최솟값이 된다.

그리고 구간을 이동할 때면 현재의 최솟값이 구간에서 빠지는지 체크한다.

Code

from collections import deque # input N, L = map(int, input().split()) arr = list(map(int, input().split())) answer = [] q = deque() # deque는 min-heap을 흉내낸다 (맨 앞 값이 구간의 최솟값) for i in range(N): # 이번에 들어갈 숫자보다 큰 숫자들은 어짜피 최솟값이 되지 못한다. # 다 pop while q and q[-1] > arr[i]: q.pop() q.append(arr[i]) # 이번에 들어갈 숫자 input # 만약 이번에 구간에서 나가는 숫자가 최솟값이라면 deque에서 빼준다 if i >= L and q[0] == arr[i - L]: q.popleft() answer.append(q[0]) # deque의 맨 앞 숫자가 현재 구간에서의 최솟값 print(' '.join(map(str, answer)))

슬라이딩 윈도우 방식으로 구현하면 코드도 더 짧고 O(N) 안에 해결할 수 있다.

from http://be-simon.tistory.com/5 by ccl(A) rewrite - 2021-07-27 23:26:34