11003번 - 최솟값 찾기(c++)

 

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

문제 요약

• 길이 N의 수열이 주어진다.
• 각 위치 i에서, 그 위치를 포함한 직전 L개의 숫자 중 최솟값을 구해라.
• 출력은 수열의 처음부터 끝까지 각 위치에서의 최솟값을 공백으로 구분하여 출력.

보니까 슬라이딩윈도우를 사용하는건 맞다. 근데 최솟값을 찾아야하니 정렬을 해야할건데 

전부 정렬을 했다간 n의 크기가 최대 5,000,000이라 시간초과가 무조건 날거같았다.

그래서 찾아보니까 deque 라는걸 사용한다더라.
deque를 사용해서 정렬 비슷한 효과를 낼 수 있는데, 아래 2번에서 설명하겠다.

---

 

1. 인덱스와 값을 저장하기 위한 pair<int, int>

처음엔 그냥 숫자만 넣으려 했는데,
슬라이딩 윈도우의 범위가 현재 인덱스 기준 i - L + 1부터 i까지이기 때문에
값과 함께 인덱스도 저장해야 범위를 쉽게 체크할 수 있다.

그래서 다음처럼 pair<int, int>를 정의했다:

typedef pair<int, int> Node;
deque<Node> deque;

 

2. 들어오는 값보다 큰 값은 모두 제거

값이 하나 들어올 때마다,
deque의 뒤에서부터 현재 값보다 큰 값은 모두 제거한다.

왜냐하면:

• 어차피 현재 값이 더 작으니 앞으로 최솟값 후보가 될 가능성이 높고
• 큰 값들은 남아있을 이유가 없다

while (deque.size() > 0 && deque.back().second > num) {
    deque.pop_back();
}

이 과정을 반복하면 맨뒤에 들어오는 Node의 숫자 데이터는 항상 앞에 남아있는 Node의 숫자 데이터보다 크기 때문에  오름차순 정렬 상태처럼 유지된다.

따라서 deque.front().second가 항상 최솟값이 된다.

---

✅ 3. 슬라이딩 윈도우 범위를 벗어난 값은 제거

값을 다듬고 deque에 추가한 뒤,
앞쪽(front)의 인덱스가 현재 슬라이딩 윈도우 범위를 벗어났는지 확인해서 제거한다.

if (deque.front().first <= i - l) {
    deque.pop_front();
}

이 조건을 실수로 앞에 두고 실행했더니 deque가 비어 있을 수도 있어서 에러가 났다.
그래서 삽입을 먼저 하고, 이후 범위 검사 순서로 수정했다.

 

deque 상태 변화 표

 

i	입력값	동작 설명	deque 상태 (index:value)	출력값
0	1	첫 값 삽입	(0:1)	1
1	5	5 > 1 → 그대로 삽입	(0:1), (1:5)	1
2	2	5 > 2 → (1:5) 제거 후 삽입	(0:1), (2:2)	1
3	3	3 > 2 → 삽입 index 0은 범위 벗어남 → 제거	(2:2), (3:3)	2
4	6	6 > 3 → 삽입	(2:2), (3:3), (4:6)	2
5	2	6 > 2 → 제거 3 > 2 → 제거 2 == 2 → 그대로	(2:2), (5:2) → (2:2)는 범위 벗어남 → 제거	2
6	3	3 > 2 → 삽입	(5:2), (6:3)	2
7	7	7 > 3 → 삽입	(5:2), (6:3), (7:7)	2
8	3	7 > 3 → 제거	(5:2), (6:3), (8:3) (5:2)는 범위 벗어남 → 제거	3
9	5	5 > 3 → 삽입	(6:3), (8:3), (9:5)	3
10	2	5 > 2 → 제거 3 > 2 → 제거	(6:3), (10:2) (6:3)는 범위 벗어남 → 제거	2
11	6	6 > 2 → 삽입	(10:2), (11:6)	2

 

---

최종 코드

#include <iostream>
#include <deque>

using namespace std;

typedef pair<int, int> Node;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, l;
    cin >> n >> l;

    deque<Node> deque;

    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;

        // 뒷부분 정리 (현재 값보다 큰 값 제거)
        while (deque.size() > 0 && deque.back().second > num) {
            deque.pop_back();
        }

        // 새 값 추가
        deque.push_back(Node(i, num));

        // 슬라이딩 윈도우 범위를 벗어난 값 제거
        if (deque.front().first <= i - l) {
            deque.pop_front();
        }

        // 현재 윈도우의 최솟값 출력
        cout << deque.front().second << " ";
    }

    return 0;
}

---

출력 예시

입력:

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

출력:

1 1 1 2 2 2 2 3 3 3 2 2