백준 11003 최솟값 찾기 [C++, JAVA]

작성일 | In |

Problem : 최솟값 찾기

유형 : 덱, 슬라이딩 윈도우

문제 해석

  • N이 500만 이므로, O(NlogN) 이내의 시간 복잡도내에 해결해야한다.
  • 문제는 굉장히 직관적이다.
    • M 구간내의 최솟값을 구하라.
    • M이 2라면 {3, 4, 2} 가 있을때 최솟값은 3, 3, 2 가 된다.
      • {3} 3
      • {3,4} 3
      • {4,2} 2

해결 전략

  • 지금 관심 있는것은 구간 내 최솟 값 이다.
    • 구간내에 새로운 숫자가 들어올때, 이 새로운 숫자가 이전의 최솟값보다 작은지 여부만 확인하면 된다.
    • 그리고 이 새로운 숫자는 나중에 최솟값이 될 가능성이 존재하는 숫자이므로 일단 보관해야 한다.
    • 그 이전의 최솟값을 모노톤 스택 을 이용하여 오름차순으로 정렬한 상태를 유지하고 O(1)에 구할수 있다.
  • 새로운 숫자는 1개씩 들어온다.
    • 최솟값은 항상 맨앞에 있다.
    • 새로운 숫자의 구간진입으로 인해 이전의 최솟값이 outdate 된다면, 가장 앞에 있는 원소를 O(1)에 제거하기 위해 덱 자료 구조를 이용한다.

설계, 구현

  • 스택(덱) 에 넣는 정보는 {등장 인덱스 위치, 값} 두가지로 관리한다.
  • 새롭게 등장한 숫자가, 스택(덱)의 top(back) 보다 작다면, 이후 나오는 숫자들은 현재 top(back)의 숫자를 볼 필요도 없어진다.
    • (back pop)을 해준다.
  • 만약 구간의 길이가 2이고, 새로 들어오는 숫자의 등장 인덱스가 5이면 4 미만의 위치 인덱스를 가진 인덱스는 구간내에 있으면 안된다
    • 즉 이전의 최솟값(front)이 새롭게 들어온 최솟값보다 작아도, 인덱스가 구간 범위 밖이라면 삭제(front pop)을 해준다.

주의할 점

  • N이 몹시 크다.
  • N이 큰 상수의 경우에도 조심해야 하므로 O(NlogN) 풀이는 위험할 수 있다.

코드 (c++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

bool isValidIndex(int frontIndex, int indexPivot) {
    return frontIndex > indexPivot;
}

void solve() {
    int n, m;
    cin >> n >> m;

    deque<pii> dq;
    for (int idx = 0; idx < n; ++idx) {
        int num;
        cin >> num;

        while (!dq.empty() and dq.back().second >= num) {
            dq.pop_back();
        }
        dq.push_back({ idx, num });

        if (!isValidIndex(dq.front().first, idx - m)) {
            dq.pop_front();
        }
        cout << dq.front().second << " ";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    //freopen("input.txt", "r", stdin);

    solve();

    return 0;
}

코드 (java8)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {

    public static Deque<Pair> window = new ArrayDeque<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int numCount = Integer.parseInt(st.nextToken());
        int windowSizeLimit = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());

        for (int index = 0; index < numCount; ++index) {
            int num = Integer.parseInt(st.nextToken());
            pushToWindow(index, num);
            eraseRangeOutIndex(index - windowSizeLimit);

            int minNumber = getMinValueInWindow();
            bw.append(minNumber + " ");
        }

        bw.flush();
        br.close();
        bw.close();
    }

    public static void pushToWindow(int index, int num) {
        while (!window.isEmpty() && window.getLast().getNumber() >= num) {
            window.pollLast();
        }
        window.addLast(new Pair(index, num));
    }

    public static void eraseRangeOutIndex(final int minValidIndex) {
        if(!isValidIndex(window.getFirst().getIndex(), minValidIndex)){
            window.pollFirst();
        }
    }

    public static boolean isValidIndex(final int windowFrontIndex,final int minValidIndex) {
        return windowFrontIndex > minValidIndex;
    }

    public static int getMinValueInWindow(){
        return window.getFirst().getNumber();
    }
}

class Pair {
    private int index;
    private int number;

    Pair(int index, int number) {
        this.index = index;
        this.number = number;
    }

    public int getIndex() {
        return index;
    }

    public int getNumber() {
        return number;
    }
}

피드백

  • 사실 이 문제를 다른 저지에서 BST를 이용해 O(NlogN) 풀이로 해결한 경험이 있다.
  • 힙 자료구조를 이용한 풀이도 가능해보인다.