최솟값 찾기(BOJ 11003)

문제

이미지 클릭

문제 설명

이 문제는 deque을 이용하여서 값들을 deque에 넣어주고 만약 deque의 원소의 개수가 입력받은 숫자보다 더 커지게 된다면 deque의 앞에 있는 숫자를 뻬고 뒤에 숫자를 넣어주면서 최솟값을 갱신해 나가는 문제입니다. 하지만 deque에 모든 숫자를 넣어가면서 최솟값을 확인해 나간다면 시간초과가 발생하기 때문에 입력받는 자연수와 그 자연수의 인덱스값을 deque에 넣어서 최솟값을 찾아 주었습니다. 자세한 내용은 아래에서 설명드리도록 하겠습니다.

전체 코드

#include <bits/stdc++.h>
using namespace std;
int n, m;//n:입력받는 자연수 개수, m:덱 내부의 자연수 최대 개수
deque<pair<int, int>> dq;
int main() {
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    int x;
    cin>>x;
    if(dq.size() && dq.front().second <= i - m)dq.pop_front();//덱이 m을 넘어가는지 확인
    while (!dq.empty() && dq.back().first > x)dq.pop_back();//dq내부 최솟값 탐색
    dq.push_back({x, i});
    cout << dq.front().first << " ";
  }
}

문제 해설

우선 위에서 말씀 드린 것처럼 dq(x, index) 형식으로 deque을 만들어 줄 것입니다.

deque<pair<int, int>> dq;

 

그런 다음 길이 n과 deque의 최대 크기 m을 입력받고 최솟값을 탐색을 시작할 것입니다.

for문 내부가 굉장히 중요한데, 젤 먼저 첫번쨰 if문에서는 dq가 비어있지 않고, index(dq.front(). second) 값이 i-m보다 같거나 작으면 맨 앞에 있는 값을 제거한다는 것을 의미합니다. 즉 i번째 인덱스까지 도달하였고, 만약 i-m 보다 같거나 작다는 뜻은 최솟값 범위에서 제외되기 때문에 멘 앞에 있는 값을 제거해 주는 것입니다.

if(dq.size() && dq.front().second <= i - m)dq.pop_front();

 

그런 다음 while문을 만나게 되는데, 여기에서 중요한 것은 dq에 들어 있는 값보다 x가 더 작다면 dq에 들어 있는 값들 중에서 최근에 들어간 것들부터 차례대로 제거해 나가야 합니다. 만약 x가 더 커진다면 그때 while문을 멈추면 됩니다. 그러고 나서 dq의 맨 앞에 있는 값을 출력해 주면 최솟값 탐색을 완료할 수 있습니다.

while (!dq.empty() && dq.back().first > x)dq.pop_back();
dq.push_back({x, i});
cout << dq.front().first << " ";

 

회고

이번 문제를 풀어보고 비교적 쉽게 풀줄 알았지만 비교적 구현하는데 시간이 조금 오래 걸렸고, 시간초과가 여러 번 떠서 문제를 어떤 방식으로 최적화해야 할지 고민을 많이 한 문제였다. 특히 코드의 길이를 줄이기 위해서 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); ← 이 녀석을 사용하지 않았다가 시간초과가 떳지만 사용해 보니 시간초과가 해결되기도 하였다. 또한 이 문제와 비슷한 히스토그램도 풀어본다면 자료구조 문제들을 공부하는데 많이 도움이 될 것 같다.