[BOJ/pypy] 25603번 짱해커 이동식

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

25603번: 짱해커 이동식

문제 해석

비용이 주어졌을 때 최대 비용의 최솟값을 출력한다.

---

코드

from collections import deque
import sys
input = sys.stdin.readline

a,b = map(int, input().split())
array = list(map(int, input().split()))
min_array = deque([0])
count = 0

for i in range(a+1-b):
    min_array.append(min(array[i:i+b]))
    if min_array[0] <= min_array[-1]:
        min_array.popleft()
    else:
        min_array.pop()

print(min_array[0])

---

문제 풀이 (풀이방법은 여러가지일 것이다. 대회 중 풀었던 방법을 기준으로 설명한다.)

위 코드를 생각하지 말고, 입/출력 예시를 보자.

 

두 번째 줄에 입력될 5개를 순서대로 리스트화 시켜보자.

[1, 3, 5, 4, 2] 이다.

 

이제 이를 첫 번째 줄 두 번째 값 2의 범위로 조건에 맞게 슬라이딩 윈도우를 해보면

 

1과 3을 비교했을 때에는 1이 더 작기 때문에 1일 것이다.

3과 5를 비교했을 때에는 3이 더 작기 때문에 3일 것이다.

5와 4를 비교했을 때에는 4가 더 작기 때문에 4일 것이다.

4와 2를 비교하면 2가 더 작기 때문에 2일 것이다.

 

이렇게 더 작은 것들을 리스트로 만들어 보자.

[1, 3, 4, 2]

 

최소 비용의 최댓값이므로 max([1, 3, 4, 2])이면 4이다.

 

그런데, 이렇게만 하면 분명히 시간초과가 뜬다.

왜일까?

 

N, K는 1 이상 10만 이하의 자연수가 될 수 있다.

따라서 리스트가 너무 커지게 되면 탐색하는데 너무 많은 시간이 걸려 시간초과가 날 수 있다.

 

그래서 나는 덱을 사용했다.

리스트에서의 0번 인덱스 요소를 제거하는 속도와 덱에서의 popleft의 속도를 비교하면 덱이 훨씬 빠르기 때문이다.

 

최소 비용에서 max값을 구하는 것이기 때문에, 최소 비용을 덱으로 구성하고, 들어온 최소 비용 값을 비교해 더 큰 값만 저장하고 작은 값은 popleft했다.

(이렇게 해도 python에서는 시간초과가 떠버려 pypy로 했다.)

 

물론 정석적인 방법은 이게 아니겠지만, 슬라이딩 윈도우와 덱으로도 풀 수 있는 문제였다.

(대회 끝난 직후 문제를 확인했을 때에는 알고리즘 분류에 이분 탐색과 매개변수 탐색만이 있었는데, 다시 보니까 더 늘어났다..)