[백준] 2812번: 크게 만들기 (C++)

문제 링크

2812번: 크게 만들기

---

제가 요즘 자신없어하는 알고리즘 종류가 그리디 문제입니다.

그래서 그리디 문제를 여러개 풀며 공부하던 도중, 재밌는 문제를 하나 발견해서 풀이를 올려보겠습니다!

풀이

모노톤 스택을 이용해서 그리디로 풀면 됩니다.

모노톤 스택을 한마디로 말하자면, 스택 원소들을 오름차순 또는 내림차순으로 유지시키는 스택입니다.

이 성질을 이용해서, 다음과 같은 과정으로 문제를 풀이했습니다.

1. true면 결과값에 포함하지 않을 chk 배열을 선언합니다.
   예를 들면, [1, 2, 3, 4] 이라는 배열이 있고, chk 배열이 [true, true, false, false] 이면 [3, 4]가 결과값입니다.
2. 내림차순 모노톤 스택을 구성합니다.
   스택에는 결과값에 포함하지 않을 후보가 될 인덱스들이 저장되고, pop될 때 chk[stack.top()]를 true하고 k--를 합니다.
3. 문자열을 다 체크했어도 k값이 남았을 때, 문자열의 뒤부터 chk 배열에서 false인 값들을 true로 바꿔줍니다.
   문자열 앞부분은 모노톤스택에 의해 큰 숫자만이 남았을 것이기 때문에 뒤에서부터 바꾸어 줍니다.

풀이코드

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

void solve() {
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;

  bool chk[n] = {};
  stack<int> st;
  for (int i = 0; i < n; i++) {
    while (!st.empty() and s[st.top()] < s[i] and k > 0) {
      chk[st.top()] = true;
      st.pop();
      k--;
    }
    st.push(i);
  }
  if (k > 0) {
    for (int i = n - 1; i >= 0; i--) {
      if(!chk[i]) {
        chk[i] = true;
        k--;
      }
      if (k <= 0) break;
    }
  }
  for (int i = 0; i < n; i++) {
    if (!chk[i]) cout << s[i];
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
  solve();
  return 0;
}

 

 

배운점

• 아직 그리디에 대해 잘 파악하지 못했지만, 이번 문제를 통해 그리디의 감을 약간이라도 올릴 수 있었습니다.
• 모노톤 스택에 대해 다시 복습할 수 있었습니다.

---

부족한 글 봐주셔서 감사합니다. 🙇

풀이와 코드에 부족한 점이나 추가하면 좋을 점이 있으면 댓글 주세요!