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

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

1306번: 달려라 홍준

 

Difficulty : Platinum 5

 

Status : Solved

 

Time : 00:12:59

 

---

 

문제 설명

 

 

홍준이는 러너이다. 그런데 어쩌다 보니 아무리 뛰어도 뛰어도 속도가 변하지 않는다. 1초에 딱 1칸을 움직인다.

그런데 홍준이가 뛰는 코스는 광고판으로 가득하다. 광고판은 빛의 세기가 다른데, 홍준이는 자신이 볼 수 있는 광고판들 중에서 가장 강렬한 빛의 광고판만이 눈에 들어온다.

홍준이는 눈이 안좋기 때문에 빛의 세기가 강한 지점에서는 안경을 쓰고 뛰려한다. 그래서 알아야 할 것이, 뛰어가면서 보이는 광고판의 빛의 세기를 알고 싶다.

홍준이가 뛰어갈 때, 1초마다 보이는 광고판의 빛의 세기를 출력하여라.

 

 

입력 및 출력

 

입력

 

첫째 줄에는 뛰는 코스의 길이, 즉 칸수 N과 홍준이의 시야의 범위 M이 주어진다. 시야가 M이라고 하면 현재 위치에서 앞뒤로 M-1칸까지 광고판이 보이는 것이다. (1 ≤ M ≤ N ≤ 1,000,000) 두 번째 줄에는 각각 칸에 있는 광고판들의 빛의 세기가 주어진다. 빛의 세기는 1,000,000을 넘지 않는 자연수이다.

홍준이는 언제나 광고판을 2M-1개 보면서 뛰고 싶기 때문에(중심으로) M번째 칸에서 뛰기 시작해서 N-M+1번째 칸에서 멈춘다고 가정하자.

 

출력

 

뛰면서 보이는 광고판의 세기를 출력한다.

입력 예시

 

5 2
1 1 1 3 2

 

출력 예시

 

1 3 3

 

 

---

 

풀이

 

사실 이 문제는 세그먼트 트리 / 슬라이딩 윈도우로 분류되어 있다. 세그먼트 트리 특성상 구간 합 / 구간 최댓값을 구하는 시간복잡도가 O(logN)이며, 총 구간이 N에 종속되므로 총 시간복잡도는 O(NlogN)이 된다. 세그먼트 트리를 구현하고, [0, 2M-1)부터 [N-2M+1, N) 구간까지의 구간 최댓값을 반환하면 된다.

 

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

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

 

..하지만 이 문제처럼, 덱을 이용하면 매우 쉽게 풀 수 있다. 문제가 거의 유사하므로 상세한 풀이는 위 링크로 갈음하도록 한다(이 문제도 위 아이디어를 통해서 풀이하였고, 그 덕인지 난이도에 비해 빠르게 풀 수 있었다.)

 

풀이 코드

from collections import deque

N, M = map(int, input().split())
light_list = list(map(int, input().split()))
light_q = deque()
answer = list()

for i in range(2*M-1) :
  while light_q and light_q[-1][1] < light_list[i] :
    light_q.pop()
  light_q.append((i, light_list[i]))
answer.append((light_q[0][1]))

for i in range(2*M-1, N) :
  while light_q and light_q[-1][1] < light_list[i] :
    light_q.pop()
  while light_q and light_q[0][0] <= i - 2*M + 1 :
    light_q.popleft()
  light_q.append((i, light_list[i]))
  answer.append((light_q[0][1]))

print(*answer)

풀이 완료!