BAEKJOON Online Judge(BOJ) 문제입니다.
Baekjoon Online Judge
Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다.
www.acmicpc.net
문제
https://www.acmicpc.net/problem/1306
1306번: 달려라 홍준
첫째 줄에는 뛰는 코스의 길이, 즉 칸수 N과 홍준이의 시야의 범위 M이 주어진다. 시야가 M이라고 하면 현재 위치에서 앞뒤로 M-1칸까지 광고판이 보이는 것이다. (1 ≤ M ≤ N ≤ 1,000,000) 두 번째
www.acmicpc.net
내가 작성한 코드
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]
www.acmicpc.net/problem/1306 1306번: 달려라 홍준 첫째 줄에는 뛰는 코스의 길이, 즉 칸수 N과 홍준이의 시야의 범위 M이 주어진다. 시야가 M이라고 하면 현재 위치에서 앞뒤로 M-1칸까지 광고판이 보이는
lem0nad3.tistory.com
기억해야할 것
- 슬라이딩 윈도우 + 우선순위 큐
- 최근에 처음 접한 새로운 유형
- 슬라이딩 윈도우에서 최대/최소를 구할 때 활용
- 세그먼트 트리와 비교
- 위 블로그에서 구현해주신 세그먼트 트리와 실행시간을 비교했을 때, 절반 정도
- 세그먼트 트리 : 2^n + nlogn
- 최대값 세그먼트 트리 생성
- 범위 탐색 - 슬라이딩 윈도우 + 우선순위 큐 : nlogn + nlogn
- 슬라이딩 윈도우 n번 탐색, 탐색마다 pq에 값 삽입
- 최대힙이 인덱스를 벗어날 때까지 pop
'코딩테스트' 카테고리의 다른 글
[백준][재귀] 감소하는 수 (0) | 2022.04.01 |
---|---|
[백준][재귀] Choose Your Own Arithmetic (0) | 2022.04.01 |
[백준][재귀] 종이의 개수 (0) | 2022.03.24 |
[백준][세그먼트트리] 최솟값과 최댓값 (0) | 2022.03.23 |
[백준][누적합] 나머지 합 (0) | 2022.03.22 |