[백준][슬라이딩윈도우] 달려라 홍준

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

1306번: 달려라 홍준

 

내가 작성한 코드

import sys
from heapq import heappush, heappop

read = sys.stdin.readline

def read_data():
    N, M = map(int, read().rstrip().split())
    optical = list(map(int, read().rstrip().split()))
    return N, M, optical

def sliding_window(N, M, optical):
    answer = []

    pq = []
    for i, opt in enumerate(optical[:2*M-1]):
        heappush(pq, (-opt, i))
    answer.append(-pq[0][0])

    l, r = 0, 2*M-1
    while r < N:
        heappush(pq, (-optical[r], r))
        l, r = l+1, r+1

        while not(l <= pq[0][1] < r):
            heappop(pq)

        answer.append(-pq[0][0])

    return answer



N, M, optical = read_data()
print(*sliding_window(N, M, optical))

• 슬라이딩윈도우
  
  • 0 ~ 2M-1을 시작으로 시야 M 내의 빛의 세기 탐색
• 우선순위큐
  • (빛의 세기, 인덱스)의 최대힙
  • 매 탐색마다 인덱스 범위 외의 최대값을 pop

 

다른 사람이 작성한 코드

seg = [0 for _ in range(4040404)]
 
def init(n,s,e):
    if s == e:
        seg[n] = a[s-1]
        return seg[n]
    mid = (s+e)//2
    seg[n] = max( init(n*2,s,mid), init(n*2+1,mid+1,e) )
    return seg[n]
 
def getMax(n,l,r,s,e):
    if e < l or r < s: return 0
    if l <= s and e <= r: return seg[n]
    mid = (s+e)//2
    return max( getMax(n*2,l,r,s,mid), getMax(n*2+1,l,r,mid+1,e) )
 
n, m = map(int, input().split())
p = m*2-1 # 시야범위
a = list(map(int, input().split()))
ans = []
 
init(1,1,n)
 
for i in range(n-p+1):
    ans.append(getMax(1,1+i,i+p,1,n))
print(*ans)

• 세그먼트 트리
  
  • 최댓값 세그먼트 트리 응용

https://lem0nad3.tistory.com/24

백준 1306 - 달려라 홍준 [Python]

기억해야할 것

• 슬라이딩 윈도우 + 우선순위 큐
  
  • 최근에 처음 접한 새로운 유형
  • 슬라이딩 윈도우에서 최대/최소를 구할 때 활용
• 세그먼트 트리와 비교
  • 위 블로그에서 구현해주신 세그먼트 트리와 실행시간을 비교했을 때, 절반 정도
  • 세그먼트 트리 : 2^n + nlogn
    - 최대값 세그먼트 트리 생성
    - 범위 탐색
  • 슬라이딩 윈도우 + 우선순위 큐 : nlogn + nlogn
    - 슬라이딩 윈도우 n번 탐색, 탐색마다 pq에 값 삽입
    - 최대힙이 인덱스를 벗어날 때까지 pop