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

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

처음에 이 문제를 보자마자 map의 정렬을 이용해 개수를 세면 O(N*logN)으로 쉽게 해결되겠다는 생각이 들었다.

 

그런데 막상 문제를 풀어보니 계속 시간초과가 났다...

 

결국에 priority_queue부터 Map, Set, 등의 여러 방법을 사용하다가 Map과 priority_queue는 삽입하는 과정이 느렸던게 생각나서 Union Find를 이용해 문제를 해결했다.

 

+ Union Find로 문제를 해결한 후 deque를 이용한 더 좋은 O(N)의 풀이가 있다는 것을 발견했다 ㅠㅠ

 

사실 Union Find를 이용한 방법도 정렬을 하기 때문에 O(N*logN)의 시간복잡도를 갖게 된다.

 

임의의 배열을 비용으로 정렬하면 아래 그림과 같이 정렬이 됐다고 생각해 보자

 

$$ [(a_i, i), (a_j, j), ... (a_k, k)]$$

 

그러면 맨 앞에 있는 a_i는 i ~ i-L-1 번째 칸에서 가질 수 있는 최소 값이 된다.

 

왜냐하면 최소 비용을 기준으로 정렬했기 때문에 i구간 부터 i+L-1 구간은 a_i 보다 작은 값이 없다는 뜻이 되기 때문이다.

 

여기서 다음 최소 비용을 빠르게 계산하기 위해 Union_Find가 필요하다.

 

왜냐하면 [i, i+L-1]  구간은 최솟값이 전부 구해진 상태인데, 만약 다음에 나오는 최솟값이 a_i+1 이 나올 수 있기 때문이다.

 

이 경우에는 어떻게 진행이 되는지 그림으로 생각해보자. 

 

 

구간 [i+1, i+L-1]은 이미 더 작은 최솟값이 a_i로 존재한다.

 

그렇기 때문에 이 구간은 a_{i+1}의 값을 가질 수 없다.

 

하지만 빨간색으로 표시한 i+L 위치는 a_i가 될 수 없기 때문에 a_{i+1}값이 최솟값이 된다.

 

만약 최솟값 기록을 위해 i+1번째 부터 i+L번째 까지 직접 비교를 하며 이전에 최솟값이 기록이 되었는지 확인을 한다면, 비효율적으로 탐색을 하게 된다. (2중 for문이나 마찬가지이므로 O(N^2)이 되기 때문)

 

그렇기 때문에 i+1번째 위치에 최솟값이 기록이 되지 않은 index를 가리켜 바로 최솟값을 기록할 수 있도록 Union_Find를 사용한 것이다.

 

Union_Find를 사용하면 다음과 같이 탐색을 시작할 Index를 기록하는 vector가 만들어 진다. 

a_i 가 최솟값일 경우 구간 [i, i+L-1]은 전부 최솟값이 기록이 된 상태다.

 

그러므로 [i+1, i+L-1] 구간의 수가 나타난다면 i+L부터 기록을 시작해야한다.

 

그러므로 구간 [i+1, i+L-1]에는 i+L을 탐색하도록 index를 변경해 준다.

 

 

이후 a_{i+1}이 최솟값으로 등장하면 마찬가지로 nextIdx [i+L] 에 저장된 값을 i+L+1 로 변경한다.

 

 

이렇게 Union-Find를 이용해 탐색을 시작할 index를 가리켜 최솟값을 찾아 문제를 해결했다.

 

 

+ deque를 이용한 풀이방법은 더 빠르고 간단하다.

deque는 항상 앞에 있는 수가 가장 작으며, 수가 같다면 index가 큰 수가 온다.

i번째 수가 나왔을 때 deque의 맨 뒤의 수 a와 비교하고, i번째 수가 더 작다면 a를 제거한다.

(왜냐하면 i번째 수가 deque의 맨 뒤 수 a보다 작기 때문에 구간 [i ~ i+L-1] 에는 a가 최솟값이 될 수 없기 때문)

 

i번째 수보다 큰 수를 deque에서 제거했다면, deque의 맨 앞에 있는 수가 구간의 범위를 벗어났는지 확인한다.

(범위를 벗어났다면, 더 이상 최솟값이 될 수 없기 때문이다.)

 

이러한 방법으로 문제를 풀면 O(N)으로 해결할 수 있게 된다.

 

 

​

[Union Find 아이디어 정리]

1. 최솟값을 기준으로 정렬을 한다.
2. 이후 최솟값 a_i를 뽑은 뒤 [i ~ i+L-1]의 구간 중 최솟값이 기록되지 않은 구간의 최솟값을 전부 a_i로 바꾼다.
3. 그리고 최솟값이 기록된 구간은 최솟값이 비어있을 수 있는 위치인 i+L을 가리키도록 한다.
4. 새로운 최솟값 a_k가 나오면 Union-Find로 k구간에서 탐색을 시작할 index를 찾고, 그 index부터 k+L-1까지 탐색을 하며 최솟값이 기록되지 않은 구간을 a_k값으로 기록한다. (중간에 최솟값이 기록된 구간이 나오면 break 한다. 항상 왼쪽에서 오른쪽으로 기록을 하기 때문에 최솟값이 기록된 구간 오른쪽은 이미 기록이 됐기 때문)

 

 

 

Code

 

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
#include <unordered_map>
#include <set>
using namespace std;

const int INF = 1987654321;


int FindNext(int nowIdx, vector<int> &nextIdx, int N)
{
    if (nowIdx==N)
    {
        return N;
    }
    if (nowIdx == nextIdx[nowIdx]) { 
        return nowIdx; 
    }
    return nextIdx[nowIdx] = FindNext(nextIdx[nowIdx], nextIdx, N);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int N, L;
    cin >> N >> L;
    vector<pair<int, int>> v(N);
    vector<int> nextIdx(N, INF);
    for (int i = 0; i < N; i++) {
        cin >> v[i].first;
        v[i].second = i;
        nextIdx[i]=i;
    }


    vector<int> answer(N, INF);
    sort(v.begin(), v.end(), [](pair<int, int> a, pair<int, int> b) {
        return a.first < b.first; });
    int tmpN, maxN;
    for (int i = 0; i < N; i++) {
        tmpN = FindNext(v[i].second, nextIdx, N);
        maxN = min(N, v[i].second + L);
        if (tmpN==N)
        {
            continue;
        }
        else {
            for (int j = tmpN; j < maxN; j++) {
                if (answer[j] != INF) {
                    break;
                }
                answer[j] = v[i].first;
                nextIdx[j] = maxN;
            }
        }
    }
    for (int j = 0; j < N; j++) {
        cout << answer[j] << " ";
    }

    return 0;
}

 

---

Union-Find로 문제를 풀었더니 정말 아슬아슬하게 시간에 들어왔다.

괜히 O(N * logN)으로 될 것 같아서 억지로 풀었더니 요상한 풀이가 나온것 같다;;

O(N)으로 풀 수 있는 방법이 왜 바로 안떠올랐을까 ㅠㅠㅠ