[ 백준 11003 ] 최솟값 찾기 (C++)

백준의 최솟값찾기(11003) 문제이다.

[ 문제 바로가기 ]

 

[ 문제풀이 ]

하나의 수열과 해당 수열에서 탐색을 할 범위가 주어졌을 때, 해당 범위 안에서 최솟값들을 순차적으로 출력해야 하는 문제이다.

문제를 해결하기 위해 사용한 자료구조부터 어떤식으로 진행되는지 순차적으로 알아보자.

 

#1. 자료구조 Dequeue를 이용한 접근

본인은 이 문제를 자료구조 Dequeue 를 이용해서 접근해 보았다.

자료구조 Dequeue는 Queue와 다르게 삽입을 앞이나 뒤 중에 원하는 곳에 삽입이 가능하며, 삭제 또한 가장 앞에 있는 데이터를 삭제할 수 도있고 가장 마지막에 있는 데이터를 삭제할 수도 있는 자료구조이다.

그렇다면 지금부터는 Dequeue를 어떻게 활용했는지에 대해서 이야기해보자.

가장 먼저 본인은 Dequeue에 저장되어 있는 데이터 중, 가장 앞에 "현재 구간에서의 최소값을 저장" 시켜 주었다.

그리고 가장 앞에 있는 데이터를 제외한, 그 나머지 데이터들은 그 "다음 구간에 있을 최소값들의 후보들을 저장" 시켜 주었다.

문제에 나와있는 예시로 한번 진행해보자.

[ 1 5 2 3 6 2 3 7 3 5 2 6 ] 이라는 수열이 주어졌고, 이 때 L = 3 인 경우이다.

현재 Dequeue의 상황은 아무것도 없을 테니 [ ] 이런 상황일 것이다.

편의상 [ 가장 앞쪽에 있는 원소 , 가장 마지막에 있는 원소 ] 로 Dequeue의 상태를 표기하겠다.

 

가장 처음 원소 '1'을 만나게 된다. 주어진 길이 L을 이용해서 비교를 해보면  최소값을 찾아야 할 범위는 -1 ~ 1이 된다.

문제의 조건에 맞게 범위를 수정해보면 1 ~ 1 에서의 최소값을 찾으면 되는 경우이다.

현재 Dequeue에는 비교할 대상이 없으니 자연스럽게 '1'이 현재 최솟값이 될 것이다. 그리고 Dequeue에 이 값을 삽입을 하게 되면 다음과 같아질 것이다.

[ 1 ]

두 번째 원소 '5'를 보자. 최소값을 찾아야 할 범위는 0 ~ 2 이므로, 1 ~ 2가 된다.

현재 Dequeue에는 '1'이라는 데이터가 하나 존재하고, 1 ~ 2의 범위에서 최솟값은 '1'이 된다. 즉 ! 현재 구간에서의 '5'는 최소값이 될 수가 없다. 하지만 '5'를 이대로 버릴 수는 없다. 왜냐하면 이 다음 구간도 생각을 해야 하기 때문이다.

그렇다면, 지금까지의 탐색 결과로만 본다면, 그 다음 구간에 있는 최소값들의 후보는 뭐가 될까 ?? 바로 '5'가 될 것이다.

왜 ?? 현재 최솟값은 '1'이지만, 이 '1'은 1번 Index에 존재하는 데이터이고, 1번 Index의 범위를 초과해서 2번 Index부터 ~ X번 Index까지의 데이터를 찾게 될 경우, 이 '1'은 더 이상 의미가 없어지는 데이터 이기 때문이다.

그렇기 때문에 현재까지의 탐색 결과로만 본다면, 그 다음 구간에 있을 최솟값의 후보로는 '5'가 선택될 수 있다.

그럼 이 다음 구간에 있을 최솟값의 후보로 '5'를 삽입해 주는 것이다.

[ 1 5 ]

세 번째 원소 '2'를 보자. 최소값을 찾아야 할 범위는 1 ~ 3이 된다.

현재 Dequeue에는 '1'과 '5'가 존재한다. 1과 5 모두 현재 탐색해야 할 범위인 1 ~ 3 에 속하는 데이터들이다.

그럼 이 때의 최솟값은 '1'이 될 것이다. 그런데 ! 이 다음 구간에서의 최솟값은 어떻게 될까 ???

이 다음 구간을 미리 적어본다면 2 ~ 4 구간에서의 최솟값일 텐데, 아직 4번 데이터는 탐색을 하지 안했으므로 일단 고려는 하지 말아보자. 그렇다면 ! 현재 까지 탐색 결과로만 봤을 때 2 ~ 4 구간의 최솟값은 어떻게 될까 ?? 바로 '2'가 될 것이다.

기존까지는 '5'였지만 이번에 등장하는 '2'에 의해서 다음 구간의 최솟값 후보가 바뀌게 되는 것이다.

이제 '5'는 더 이상 다음 구간의 최솟값 후보가 될 수도 없는 존재가 되어버렸다. 그러므로 '5'를 삭제하고 대신 '2'를 삽입해주자.

[ 1 2 ]

네 번째 원소 '3'을 보자. 최소값을 찾아야 할 범위는 2 ~ 4가 된다.

현재 Dequeue에는 '1'과 '2'가 존재한다. 그런데 ! 지금 Dequeue에 존재하는 '1'은 의미가 있는 데이터일까 ??

더 이상 '1'은 자신이 속한 범위에 대한 연산이 모두 끝났기 때문에 더 이상 의미가 없는 데이터가 되어 버렸다.

즉 ! Dequeue에 더 이상 존재할 이유가 없어진 것이다. 따라서, '1'을 삭제해주어야 한다. 삭제를 하면 Dequeue의 상태는 [ 2 ] 와 같을 것이다. Dequeue에 존재하는 '2'는 3번째 있는 데이터로써 현재 탐색 구간인 2 ~ 4 에 속하는 데이터이다.

현재 탐색값인 '3'과 비교를 해 봤을 때, '2'가 더 작은 값이므로 '3'은 현재 구간에서의 최소값이 될 수가 없다.

하지만 ! 두 번째 원소인 '5'와 같은 이유로 지금 여기서 버릴 수는 없는 데이터이다. 왜냐하면 이 다음 구간에서의 최솟값이 될 수 있는 후보이기 때문이다. 따라서 '3'을 Dequeue에 넣어주자.

[ 2 3 ]

이런식으로 Dequeue를 이용해서 데이터를 삽입하고 삭제를 반복해 나갈 것이다.

그렇다면, 이 부분을 코드로 한번 살펴보자.

1	deque<pair<int, int>> DQ;
2	for (int i = 1; i <= N; i++)
3	{
4		if (DQ.empty() == false)
5		{
6			if (DQ.front().second < i - L + 1) DQ.pop_front();
7		}
8		while (DQ.empty() == false && DQ.back().first > Arr[i]) DQ.pop_back();
9		DQ.push_back(make_pair(Arr[i], i));
10		cout << DQ.front().first << " ";
11	}

먼저 line1)의 DQ를 선언한 자료형부터 살펴보자.

pair<int, int> 로 선언해줌으로써 2개의 int형 데이터를 쌍으로 관리해 주었다.

그렇다면 이 int형의 쌍에 들어갈 데이터는 무엇일까 ??

바로, "해당 배열의 값" 과 "해당 배열의 인덱스 값" 이 된다.

배열의 값은 뭐 실제로 최솟값을 찾는데 비교를 해야 하니까 필요한다고 하더라도, 해당 배열의 인덱스 값은 왜 필요할까 ?? 바로, "지금 Dequeue에 들어가 있는 이 데이터가 현재 구간을 탐색할 때 영향을 미칠 수 있는 데이터인가" 판단을 하기 위함이다.

위에서 예시를 가지고 설명할 때, 4번째 원소인 '3'을 만났을 때, Dequeue에 들어있던 '1'이 삭제되는 과정이 있었다.

왜냐하면, 그 '1'은 더 이상 탐색 구간에 있어서 영향을 미칠 수 없는 데이터 였기 때문이다.

영향을 미칠 수 없다라는 판단을 "인덱스 번호를 이용"해서 판단하는 것이다.

따라서 pair<int, int> 형으로 선언을 해 주었따.

 

line6)에서 보면, "인덱스 번호를 통해서 현재 탐색 구간에 영향을 미칠 수 있는 데이터인지 아닌지" 를 판단하는 조건문이 있다.

line8)에서 보면, "현재 구간에서의 최솟값이 되는지와 다음 구간에서의 최솟값의 후보가 될 수 있는지" 에 대해서 판단하는 조건문이 있다.

위와 같이, 구간에 대해서 데이터를 판단하고 삭제를 하는 연산은, pop_front() , 구간에 대해서 최솟값의 후보가 도리 수 있는지에 대해 판단하는 연산은 pop_back() 그리고 실제로 데이터 삽입은 push_back(), 실제 최소값은 front()에서 하기 위해서 Dequeue를 이용해서 구현하였다.

 

[ 소스코드 ]

#include <iostream>
#include <vector>
#include <queue>
 
#define endl "\n"
#define MAX 5000010
using namespace std;
 
int N, L;
int Arr[MAX];
 
void Input()
{
    cin >> N >> L;
    for (int i = 1; i <= N; i++) cin >> Arr[i];
}
 
void Solution()
{
    deque<pair<int, int>> DQ;
    for (int i = 1; i <= N; i++)
    {
        if (DQ.empty() == false)
        {
            if (DQ.front().second < i - L + 1) DQ.pop_front();
        }
        while (DQ.empty() == false && DQ.back().first > Arr[i]) DQ.pop_back();
        DQ.push_back(make_pair(Arr[i], i));
        cout << DQ.front().first << " ";
    }
    cout << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}