[PS] 백준 - 최솟값 찾기 (11003번)

DevSWYoon·2023년 1월 16일
0

백준 문제풀이

목록 보기
1/7
post-thumbnail

0. 문제 소개


문제 링크 : https://www.acmicpc.net/problem/11003

길이가 N 인 배열 A 와 배열 D 에 대해
D[i] = min(A[i-L+1 : i]) 일 때, 배열 D 을 출력하도록 하는 문제이다.

(N = [L,5,000,000], L = [1,N], A[i] = [-10^9, 10^9], 시간 제한 = 2.4s, 메모리 제한 = 512MB)

I. 접근


우선, 단순히 N 과 L 에 대한 2중 for 문으로 문제를 풀면, N 과 L 의 최대값이 5*10^6 이기에 제한시간인 2.4초 내에 실행할 수 없다.

그렇다면, 문제에서 주어진 조건들을 하나씩 뜯어보며 방법을 찾아보자.
우선 원소가 변하는 배열에서 수시로 최솟값을 구하는 가장 좋은 방법은 우선순위 큐일 것이다.

두번째로 살펴볼 조건은, D의 index가 1 증가할 때 마다, 우선순위 큐가 대상으로 하는 배열에서 A[i-L] 의 원소는 제거되고, A[i] 의 원소가 추가된다는 것이다.
원소를 추가하는 것은 간단하지만, 우선순위 큐에서 원하는 원소를 제거하는 것은 너무 어렵고, 시간 역시 많이 소요된다.
그러나 만약 대상 우선순위 큐의 top 에 제거할 원소 값이 있다면, 정말 간단해질 것이다.
이를 잘 생각해보면, index 가 i 일 때, 제거해야할 원소의 값이 D[i] 의 올바른 값보다 크다면, 굳이 index 가 i 일 때 제거하지 않아도 D[i] 의 값에 지장을 주지 않는다는 것을 의미하고, 이를 통해 제거 해야할 원소의 값이 현재 index 의 D[i] 값 보다 크다면, 이후의 D[i] 값 보다 작아져 우선순위 큐의 top 까지 오게되었을 때 해당 원소의 값을 제거할 수 있다.

위에서 언급한 내용을 이용해 제거해야할 두개 이상의 원소들 중 가장 작은 값이 제일 먼저 대상 우선순위 큐의 top 에 먼저 노출될 것이기에 제거해야할 원소들 중 가장 작은 값을 가진 원소가 우선순위를 가져야하기에 제거해야할 원소들을 저장하는 자료구조 역시 우선순위 큐를 사용할 수 있다.

II. 코드 작성


#include <iostream>
#include <queue>
using namespace std;

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int N, L;
    vector<int> arr;
    priority_queue<int> main_pq, to_erase_pq;
    cin>>N>>L;
    
    arr.resize(N);
    
    for(int i = 0; i < N; ++i)
        cin>>arr[i];
    
    for(int i = 0; i < N; ++i)
    {
        if(i >= L)
            to_erase_pq.push(-arr[i-L]);
        
        main_pq.push(-arr[i]);
        
        while(!to_erase_pq.empty() && !main_pq.empty() && main_pq.top() == to_erase_pq.top())
        {
            main_pq.pop(); to_erase_pq.pop();
        }
        
        cout<<-main_pq.top()<<' ';
    }
    
    return 0;
}

III. 제출 결과


IV. 평가 및 후기


문제에서 주어진 조건을 하나씩 뜯어서 각 조건에 맞는 문제 해결 방법을 찾는 문제라 상당히 재미있게 풀었다.
또 이렇게 우선순위 큐를 잘 활용해본 문제가 다익스트라 이후로 오랜만이라 우선순위 큐의 활용에 대한 능력을 기르는데에도 도움이 된 것 같다.

profile
재잘재잘

0개의 댓글