백준 11003번 : 최솟값 찾기 C++

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

11003번: 최솟값 찾기

 

 

시간초과 이유

ios::sync_with_stdio(0);
cin.tie(0);

입출력을 cin, cout으로 할 경우

위 두줄을 써주지 않으면 시간초과가 발생합니다.

위 두줄에 대한 설명은 하단 링크를 참고하시면 됩니다.

 

https://dingcoding.tistory.com/62

ios::sync_with_stdio(false), cin.tie(0) 쓰는 이유, 백준 시간초과 해결

 

cin, cout을 사용하지 않고

scanf printf 로 입출력을 하면 통과가 되는 것 같아요.

 

 

 

---

슬라이딩 윈도우 알고리즘

 

저도 이 문제를 풀면서 이 방법이 슬라이딩 윈도우라고 하는 걸 처음 알았네요

 

1 2 3 4 5 6 7 8 9 10 11 12 13

1부터 10까지의 합은 55입니다.

 

그렇다면 2부터 11까지의 합을 구하는 방법은

 

2 , 3, 4 ... 11까지 더하는 방법과

 

1부터 10의 합에서 1을 빼고 11을 더해주는 방법이 있습니다.

 

두번째 방법을 슬라이딩 윈도우 알고리즘이라고 하네요

 

 

---

입력받는 수가 500만 정도 되기 때문에

가능하면 시간 복잡도 O(N)과 가깝게 해결해야합니다.

 

 

 

 

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

1에서 최솟값은 1

 

1 5에서 최솟값은 1

 

1 5 2 에서 최솟값은 1입니다

 

5 2 3의 최솟값은 2

 

2 3 6 의 최솟값은 3

 

3 6 2의 최솟값은 2

 

...

 

하다보면 작은 수만 중요하다는 걸 알게 됩니다.

 

 

숫자를 덱에 입력받으면서,

현재 입력받은 숫자보다 앞에 등장한 수가 크다면

앞에 있는 큰 수 들을 pop 해주면서 작은 숫자 위주로 저장합니다.

 

그러다보면 자연적으로 덱의 front로 작은 숫자가 밀리게 되는데

작은 숫자의 값이 구간에 해당하지 않는다면 역시 pop 해주면 됩니다.

 

 

숫자를 하나씩 받아가면서 필요없는 건 제거해주는 과정이

슬라이딩 윈도우 알고리즘과 동일합니다.

 

 

 

---

 

문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, l, arr[5000001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> l;

    deque<int> dq;

    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        arr[i] = t;

        if (dq.empty()) {
            dq.push_back(t);
        }
        else {
            while (!dq.empty() && dq.back() > t) {
                dq.pop_back();
            }
            dq.push_back(t);
        }

        if ((i - l >= 0) && (arr[i - l] == dq.front())) {
            dq.pop_front();
        }

        cout << dq.front() << ' ';
    }

}

문제 11003번