[백준 11003][💚5] 최소값 찾기 (슬라이딩 윈도우, deque)

🚀 난이도

💚 플래티넘 5

🚀 문제

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

예제 입력 1 
12 3
1 5 2 3 6 2 3 7 3 5 2 6
예제 출력 1 
1 1 1 2 2 2 2 2 3 3 2 2

🚀 내 풀이

deque라는 자료구조에 대해 처음 알게된 문제!

O(N)으로 어떻게 풀 수 있을까 싶어 고민을 했는데 의외로 우선순위큐(힙정렬)을 사용한 O(NlogN) 도 입출력 시간만 빠르게해주면 통과되었다. 500만 * 22 (500만을 log2 한 것)이 1억을 넘기 때문에 무조건 O(N)으로 해야하는 줄 알았는데 입출력 시간만 조절해주면 시간초과 안되길래 의외라고 생각했다. 아무튼! 난 고민 고민하다가 deque 를 사용하여 풀이하면 된다는 힌트를 보고나서 deque 을 공부한 후에 풀이 하게 되었다. 힙정렬을 통한 우선순위큐 풀이도 시간초과 나지 않는듯 하여 우선순위 큐(Min Heap)로 구간 내 최소값을 찾는 풀이도 해보았다.

매번 새로운 창문 안에서의 최소값을 출력해야 한다. 👉 슬라이딩 윈도우 알고리즘

🔥 deque 덱을 사용한 풀이

[STL 컨테이너] deque (+ vector와의 차이점)

deque은 맨앞에서도 맨뒤에서도 삽입, 삭제를 할 수 있다. 즉, pop_front, push_front 연산을 할 수 있다.

\(A_{i-L+1}\) ~ \(A_{i}\)구간의 길이는 L로 고정적이다. 👉 슬라이딩 윈도우 알고리즘 을 사용

• deque에는 다음, 다다음 혹은 그 이후 구간들에서 최소값이 될 수 있는 후보 원소들만 모이게 해야 한다.
  • deque 의 맨 앞의 원소는 늘 해당 구간의 최소값이 되게끔 유지 한다.
  • deque 의 원소들은 크기 순서대로 정렬을 유지하게끔 한다.
• deque 를 선택한 이유
  • 고정적인 길이의 구간(창문)을 한칸씩 옮기므로 맨앞 원소는 삭제되고 맨뒤 원소는 추가되기도 삭제되기도 해야 한다.
  • 일반 큐와는 다르게 벡터나 배열처럼 [] 를 사용하여 인덱스로 중간 원소들에도 접근할 수 있다.

• 구간 이동시
  • 뒤 (arr[i] 새롭게 deque에 추가하기)
    • 1️⃣ pop_back 👉 뒤에서 삭제
      • deque 안에 들어있는 구간 안의 원소들 中 arr[i] 와의 크기를 고려했을 때 앞으로 절대 최소값이 될 수 없는 것들 전부 삭제
      • deque의 맨 앞 원소는 늘 현재 구간의 최소값이 되도록 오름차순 정렬을 유지해야 하므로
        • 예를 들어 [3,6,7] 상황에서 4 가 들어오려한다면(현재 구간 최소값 3) 6과 7는 제거한 후에 4를 추가하여 [3,4]로 만들어야 한다. 왜냐하면 6과 7는 4보다 크므로 앞으로 4와 함께 같은 구간안에 있는한 절대 최소값이 될 수 없기 때문이다. 4 보다도 먼저 빠져나갈 것이기 때문에! 따라서 6과 7는 제거한다. 이런식으로 오름차순 정렬을 하는 것이다. 4는 3이 구간을 빠져나가고나면 다음 최소값이 될 수 있는 후보가 될 수 있다.
    • 2️⃣ push_back 👉 뒤에 추가
      • arr[i] 보다 커서 앞으로 절대 최소값 후보가 될 수 없는 원소들을 전부 제거해준 후 arr[i] 을 뒤에 추가해준다.
  • 앞 (L 길이의 구간을 벗어나므로 나갈 타이밍이 된 arr[i - L]을 deque 에서 삭제)
    • 1️⃣ pop_front 👉 앞에서 삭제
      • 구간은 모두 고정적인 L 길이를 유지해야 하므로 창문이 밀려 구간에서 벗어난다면 삭제를 해주어야 한다. 이를 큐처럼 앞에서 빠져나가도록 앞에서 삭제해야 한다.
      • 나갈 타이밍이 된 친구는 앞에서 삭제해준다.
      • 현재 i 일 때, 현재 deq에 arr[i - L] 이 들어있다면 arr[i - L]은 구간을 이제 벗어나야 하는 입장이므로 앞에서 빼내어 삭제시켜 준다.
      • deque 안에 든 원소들이 각자 자기가 구간에서 빠져 나갈 타이밍을 알아야 하기 때문에 ⭐인덱스를 알고 있어야 한다.⭐
        • deque<pair<int, int>> 로 데이터와 인덱스 함께 저장하는 것이 필요
        • 예를 들어 현재 i = 5 이며 고정적인 길이 L 이 3 이라면 deque안에 arr[2]가 있다면 arr[2]는 이제 빠져나가 삭제되야 한다. 더 이상 구간에 속하지 않기 때문이다. [2,3,4],5 에서 이제 2 [3,4,5] 가 되야하므로 2는 삭제되야 함.
    • 2️⃣ 맨앞 원소 출력
      • deque의 맨 앞 원소는 항상 현재 구간의 최소값이 오도록 유지가 되므로 그냥 현재 deque의 맨앞 원소를 출력하면 그게 바로 현재 구간에서의 최소값이다.
      • O(1)

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>

using namespace std;

struct A {
    int data; // 원소값
    int pos;  // 원소가 위치한 인덱스
};

int main() {
    /* cin, cout 입출력 속도 향상 */
    ios::sync_with_stdio(false);
    cin.tie(NULL); 
    cout.tie(NULL);

    int N, L;
    cin >> N >> L;
    vector<int> arr(N);
    for (int i = 0; i < N; ++i)
        cin >> arr[i];

    deque<A> dq;
    for (int i = 0; i < N; ++i) {
        if (!dq.empty() && i == dq.front().pos + L) // 나갈 타이밍이 된 친구는 앞에서 빠져나가도록 삭제해준다. pop_front()
            dq.pop_front();
        while (!dq.empty() && dq.back().data > arr[i]) // arr[i] 가 들어오게 됨으로써 arr[i]보다 커서 앞으로 최소값 될 일이 절대 없는 기존 deque 안의 원소들은 삭제해준다. pop_back()
            dq.pop_back();
        dq.push_back({ arr[i], i }); // arr[i] 을 추가한다. (위 pop_back()으로 인하여 arr[i]보다 더 큰건 다 삭제했으므로 오름차순 정렬을 유지한 채로 뒤에 추가되게 된다.)
        cout << dq.front().data << " "; // deque 의 맨앞 원소를 출력하면 그게 바로 현재 구간(i-L+1 ~ i)에서의 최소값 
    }
}

1 5 2 3 6 2 3 7 3 5 2 6

[]은 deque의 상황이다. ()은 이 데이터가 위치한 인덱스다. 밑줄은 현재 구간 \(A_{i-L+1}\) ~ \(A_{i}\) 에서의 최소값 (현재 deque 의 맨 앞) 취소선은 pop_front 됐거나 pop_back 된 것을 의미한다.

• i = 0 : [ ] 👉 [ 1(0) ]
• i = 1 : [ 1(0) ] 👉 [ 1(0), 5(1) ]
• i = 2 : [ 1(0), 5(1) ] 👉 [ 1(0), 2(2) ]
• i = 3 : 1(0) [ 2(2) ] 👉 [ 2(2), 3(3) ]
• i = 4 : [ 2(2), 3(3) ] 👉 [ 2(2), 3(3), 6(4) ]
• i = 5 : 2(2) [ 3(3), 6(4) ] 👉 [ 2(5) ]
• i = 6 : [ 2(5)] ] 👉 [ 2(5), 3(6) ]
• i = 7 : [ 2(5), 3(6)] ] 👉 [ 2(5), 3(6), 7(7) ]
• i = 8 : 2(5) [ 3(6), 7(7) ] 👉 [ 3(6), 3(8) ]
• i = 9 : 3(6) [ 3(8) ] 👉 [ 3(8), 5(9) ]
• i = 10 : [ 3(8), 5(9) ] 👉 [ 2(10) ]
• i = 11 : [ 2(10) ] 👉 [ 2(10), 6(11) ]

이렇게 하여 답은 1 1 1 2 2 2 2 2 3 3 2 2

🔥 우선순위 큐를 사용한 풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <queue>

using namespace std;

struct A {
    int data;
    int pos;
};

struct cmp {  // 힙정렬(우선순위큐)를 위한 비교 함수 (A 구조체를 만들어주어서 따로 비교함수 만들어주는게 필요했다.)
    bool operator()(const A& a, const A& b) {
        return a.data > b.data; // min heap 이 되게끔, 즉 최소값이 루트에 오게끔
    }
};

int main() {
    /* cin, cout 입출력 속도 향상 */
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, L;
    cin >> N >> L;
    vector<int> arr(N);
    for (int i = 0; i < N; ++i)
        cin >> arr[i];

    priority_queue<A, vector<A>, cmp> pq;
    for (int i = 0; i < N; ++i) {
        pq.push({ arr[i], i });
        int pos = pq.top().pos;
        while (pos < i - L + 1) {
            pq.pop();
            pos = pq.top().pos;
        }
        cout << pq.top().data << ' ';
    }
    return 0;
}

deque 보다 조금 더 시간이 소요되었다. min heap 을 가져서 늘 최소값을 리턴하는 우선순위큐를 만들어서 구간에 새로운 원소가 추가될 때마다 큐에 넣고 나갈 타이밍이 다되어 구간에서 범위에 벗어나야 하는 원소들은 큐에서 삭제해준다. 우선순위큐는 늘 최소값을 리턴하므로 매 구간마다 pq.top() 해주면 그게 바로 해당 구간의 최소값이다. 마찬가지로 나갈 타이밍을 알기 위해선 인덱스를 알아야하니 원소값과 인덱스를 함께 묶어 저장한다. (난 구조체를 사용)

• 우선순위 큐를 사용할 때 나가는 타이밍
  • 현재 우선순위 큐 내에서 최소값인데(top) 범위 바깥으로 벗어났다고 판단되는건 삭제해야 함
  • 최소값이 될 일이 전혀 없는 것들은 deque 처럼 굳이 큐에서 꺼내 삭제해줄 필요는 없다. 어차피 우선순위큐 안에 있어도 절대 pop 되지 않을 것이기 떄문이다.
    • 그냥 현재 우선순위큐의 최소값 top이 현재 구간에 포함되는지만 확인하면 된다. 포함되지 않는다면 버려야 함. 우선순위큐에서 pop 시켰는데 그 최소값이 현재 구간에 포함되는 최소값이 아니면 안되기 때문이다.
      • 그러니 while문으로 돌려야 하는 것이다. 지금은 우선순위 큐 내에서 최소값이 될 수 있는데 현재 범위에는 해당되지 않는 것들이 여러개가 될 수 있기 때문이다. 그런게 하나도 없을때까지 반복하여 삭제해야 함.

1 5 2 3 6 2 3 7 3 5 2 6

[] 은 우선순위큐 안의 모습, 밑줄은 현재 구간 최소값, 은 pop 된 것

• i = 0 : [ 1(0) ]
• i = 1 : [ 1(0), 5(1) ]
• i = 2 : [ 1(0), 5(1), 2(2) ]
• i = 3 : 1(0) [ 5(1), 2(2), 3(3) ]
  • 우선순위큐에서 가장 최소값(top)이 1(0) 인데 이는 범위를 벗어났으므로 pop
• i = 4 : [ 5(1), 2(2), 3(3), 6(4) ]
• i = 5 : 2(2) [ 5(1), 3(3), 6(4), 2(5) ]
  • 우선순위큐에서 가장 최소값(top)이 2(2) 인데 이는 범위를 벗어났으므로 pop
• i = 6 : [ 5(1), 3(3), 6(4), 2(5), 3(6) ]
• i = 7 : [ 5(1), 3(3), 6(4), 2(5), 3(6), 7(7) ]
• i = 8 : 2(5) [ 5(1), 3(3), 6(4), 3(6), 7(7), 3(8) ]
  • 우선순위큐에서 가장 최소값(top)이 2(5) 인데 이는 범위를 벗어났으므로 pop
• i = 9 : [ 5(1), 3(3), 6(4), 3(6), 7(7), 3(8), 5(9) ]
• i = 10 : [ 5(1), 3(3), 6(4), 3(6), 7(7), 3(8), 5(9), 2(10) ]
• i = 11 : [ 5(1), 3(3), 6(4), 3(6), 7(7), 3(8), 5(9), 2(10), 6(11) ]

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기