[백준/Baekjoon] 2812 크게 만들기 C++ :: Data Structure & Greedy

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

2812번: 크게 만들기

---

1. Logic

처음 이 문제를 봤을 때는 작은 숫자 순서대로 다 빼주면 되는 줄 알았다. Case 3을 보면 작은 수 부터 다 빼주면 477584이기 때문에 정답이 아니다. 결국 이 문제를 일반화 시켜보게 되면 알고리즘은 "현재 보고 있는 수보다 작은 수가 앞에 있으면 앞에 있는 수를 지워야 한다." 이다.

 

문제에 나온 TestCase 3을 예시로 들어 설명하자면

10 4

4177252841 

지울 수를 걸러내는 로직은 스택에 값이 있고(비어있지 않고) 숫자를 지울 수 있으며, 현재 넣을 값이 stack의 top의 위치에 있는 값보다 클 때 stack의 top의 값을 pop하고(지우고) 숫자를 지운 횟수 cnt를 늘려준다. 

1. 처음 시작할 때에는 스택이 비었기 때문에 스택에 4가 들어간다 | stack[4]

2. 스택에는 4가 들어가있고 현재 스택의 top과 비교할 숫자는 1이기 때문에 4보다 작으므로 stack에 넣어준다. | stack[41]

3. 7은 1보다 크기 때문에 스택에서 1을 지워준다. | stack[4], cnt = 1

    이후 top은 4이고 4 또한 7보다 작기 때문에 pop해주고 while문을 넘어간 후 7이 스택에들어간다. | stack[7], cnt = 2

4. 7은 스택의 top값 7보다 크지 않기 때문에 스택에 push해준다. | stack[77]

5. 2는 7보다 크지 않기때문에 stack에 push해준다. | stack[772]

6. 5는 stack의 top인 2보다 크기 때문에 2를 pop해주고 cnt++후 5를 넣어준다.| stack[775], cnt = 3

7. 2는 stack의 top 5보다 크지 않기 때문에 2를 push해준다. | stack[7752]

8. 8은 2보다 크기때문에 2를 지우고 cnt 올리고 8을 넣어준다. | stack[7758], cnt = 4

    8은 5보다 크지만 현재 cnt가 k값과 같아졌기 때문에 더이상 지울 수 없다.

9. 이후 남은 자리는 stack에 계속 push한다.

 

뒤로 갈수록 숫자가 점점 작아지는 케이스에 대해서는 while문에서의 pop연산이 발생하지 않는다.(s[i] > stack.top()의 조건을 충족하지 않기 때문에)

ex > 

4 1

4321

그렇기 때문에 이 경우 숫자가 가장 작은 뒤에서부터 stack의 성질에따라 pop해주면 된다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    string str;
    cin >> str;

    stack<char> sta;
    int cnt = 0;

    for(int i = 0; i < n; i++) {
        while(!sta.empty() && k > cnt && sta.top() < str[i]) {
            cnt++;
            sta.pop();
        }
        sta.push(str[i]);
    }
    while(cnt < k) {
        cnt++;
        sta.pop();
    }

    vector<char> ans;
    while(!sta.empty()) {
        ans.push_back(sta.top());
        sta.pop();
    }

    for(int i = ans.size() - 1; i >= 0; i--) {
        cout << ans[i];
    }
}

 

 

---

3. Feedback

자료구조 중 deque와 stack 둘다 생각해서 풀면 될 것같았지만 생각보다 로직을 떠올리는데 시간이 많이 걸렸다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐