[백준 2812 C++][G5] 크게 만들기

⭐️ 난이도

 

Gold 5

---

⭐️ 문제

https://www.acmicpc.net/problem/2812

2812번: 크게 만들기

 

 

---

⭐️ Idea flow

 

이 문제를 읽었을 때 어떻게 풀어야 할 지 감이 오지 않아서 주어진 예제를 직접 풀어보면서 규칙을 찾아보려고 했다.

처음에는 제일 작은 수 k개를 찾아서 지우면 되는 줄 알았다.

하지만 무작정 작은 수들만 골라서 지우게 되면 제일 작은 수들을 지우고 난 후, 작은 수가 큰 수 왼쪽(앞)에 있을 수 있다.

예를 들어 k=4 num=4177252841일 때, 제일 작은 수들만 골라서 지우면 477584가 나온다.

이 예시를 통해서 알 수 있는 것은 큰 수를 만났을 때, 현재 수보다 작은 수가 앞에 있으면 해당 수를 지워야 한다는 것이다.

 

그 다음 생각한 방법은 제일 큰 수를 선택하고 해당 수를 기준으로 왼쪽에 큰 수보다 작은 수가 없을 때까지 삭제를 하는 것이었다.

대략적인 접근법은 맞는것 같았지만 위와 같은 방법으로 답을 구하기엔 너무 비효율적이라는 판단을 했다.

 

하지만 이걸 어떻게 풀어야 할지 도저히 모르겠어서 다른 분들의 블로그를 참고했다.

이 문제의 key point는 stack(deque)를 사용하는 것이었다.

 

[전체적인 알고리즘]

1. 반복문으로 처음부터 마지막 원소까지 돌면서 현재의 원소와 stack(deque).top()의 원소와 비교한다.

2. 만일 현재 원소가 더 크다면(deque.top()이 더 작다면), top에 있는 수가 자신보다 작지 않을 때까지 pop을 실행한다.

   단, pop은 최대 k번까지 가능하다.

3. deque에 현재 값은 push한다.

 

---

⭐️ Code

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>

#define INF 987654321
#define MAX 1000000 + 1
using namespace std;

// 2812 - 크게 만들기
int n, k;
vector<int> nums;
deque<int> dq;

void input(){
    scanf("%d %d", &n, &k);
    nums.assign(n, 0);

    for(int i = 0; i < n; i++){
        scanf("%1d", &nums[i]);
    }
}

void solve(){
    for(int i = 0; i < n; i++){
    	// 아직 k개를 모두 제거하지 않았으며 & 자신보다 더 작은 수가 앞에 존재한다면
        while(!dq.empty() && k && dq.back() < nums[i]){
            k--;
            dq.pop_back();
        }
        dq.push_back(nums[i]);
    }
}

void printAnswer(){
    for(int i = 0; i < dq.size() - k; i++){
        printf("%d", dq[i]);
    }
}

int main(){

    input();
    solve();
    printAnswer();

    return 0;
}