BOJ 1306 : 달려라 홍준

문제 링크 : https://www.acmicpc.net/problem/1306

 

언뜻 봐서는 Sliding Window + Segment Tree 또는 Multiset 로 보인다.

구간이 1칸씩 바뀌기 때문에 구간이 바뀔 때마다 Segment Tree 또는 Multiset 으로 O(log N) 쿼리를 하면

총 시간복잡도는 O (N log N) 이다.

 

하지만 이보다 훨씬 빠른 O(N) 풀이가 있다.

deque 를 활용하면 O(N) 만에 매우 간단하게 코드를 짤 수 있다.

 

deque 에 들어갈 것은 기본적으로 (값, index) 순서쌍, 즉 pair 이다.

현재 우리가 처리하는 구간의 인덱스가 [L, R] 이라 해보자. A[L], ..., A[R] 까지의 최댓값을 구하는 것이다.

Sliding Window 알고리즘에 의해 우리는 A[L-1]까지는 고려하면 안되고, A[R]을 새로 추가하고 있다.

 

deque 의 front 로 갈수록 값이 커지게 한다면, 답은 deque.front() 에 저장되어 있을 것이다.

우리는 삽입을 deque 의 back 에서만 시행할 것이다.

 

deque 의 back 의 원소들을 하나하나 보면서, 현재 삽입할 A[R] 보다 작다면 빼버리면 된다.

A[R]이 추가된 이상, 그 이전에 등장했고 A[R] 보다 작은 수들은 더 이상 최댓값이 될 수 없기 때문이다.

 

deque의 front 에서는 인덱스가 L - 1 이하인 원소들을 pop 해주면 된다.

[L-1, R-1] 쿼리 후 즉시 A[L-1] 을 빼줄 필요가 없이, 계속 들고 있다가 front 의 index가 L-1 이 되면 제거하는 것이다.

 

소스는 아래처럼 간단하다.

void push_dq(int num, int idx){
    while(!dq.empty() && dq.front().second <= idx - k) dq.pop_front();
    while(!dq.empty() && dq.back().first < num) dq.pop_back();
    dq.push_back({num, idx});
}

첫 번째 while 에서는 낡은 index 들을 빼주고, (현재 들어오는 수인 num 과는 관계 없음)

두 번째 while 에서는 num 보다 작은 값들을 빼준다.

그 후 dq.back() 에 삽입해주면 된다.

 

모든 원소는 dq 에 한 번씩만 들어가고 한 번씩만 삭제되기에 O(N) 이면 해결할 수 있다.