[C++] 백준 온라인 저지 2812번 크게 만들기 풀이

주어지는 수에서 숫자 몇 개를 지웠을 때 가장 크게 만들 수 있는 수를 구하는 문제

 

---

문제

 

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)

둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

 

출력

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

 

 

풀이

 

 30분정도 고민해 봤는데 아이디어가 떠오르지 않아서 구글링 했습니다. 결과는...!

 

1. 최대한 큰 수가 앞으로 와야 하는데 그렇다고 무작정 가장 큰 수를 찾고 그 다음 큰 수를 찾고 ... 하는 식으로는 예제 2번부터 틀린다.

7 3
1231234

 

2. 그렇기 때문에 숫자의 처음부터 순회하면서 하나씩 비교해 나가면서 가장 크게 만들 수 있는 수를 찾아야 하는데 N의 최대값이 50만이기 때문에 O(N)에 끝낼 수 있도록 해야한다. 즉 1번만 순회해야 함. (1번을 넘어가는 순간 시간 초과를 맞이하게 될 것임...)

 

3. 예제의 정답들을 보면 앞에 있는 숫자보다 뒤에 있는 숫자가 더 크면 앞에 있는 숫자를 삭제한다. 같거나 작으면 넘어감. 따라서 맨 앞에서부터 앞뒤 숫자들을 비교하면서 지울 수 있는 횟수가 남아있는 동안 앞에 있는 숫자보다 뒤에 있는 숫자가 더 크면 앞에 있는 숫자를 삭제한다. 

 

 3-1) 만약 순회가 다 끝나기 전에 지울 수 있는 횟수를 다 썼다면 남은 숫자들은 삭제하지 않고 그냥 붙여준다. 

 

 3-2) 만약 순회가 끝났는데 지울 수 있는 횟수가 남아있다면 남은 횟수만큼 맨 뒤에 있는 숫자들을 삭제한다. 

5 2
54321

ans : 543

 

  위와 같은 경우에 순회가 끝나도 아무 숫자도 삭제되지 않는다. 이런 경우에는 남은 K(이 반례에서는 2)만큼 맨 뒤에 있는 숫자들을 삭제한다. 

 

4. N의 최대값은 50만이고 만약 K가 2와 같이 아주 작은 숫자라면 정답을 정수형으로 표현하려 하면 표현범위를 넘어가서 오버플로우가 될 것이다. 그래서 정답은 배열에 저장해 놓은 뒤 cout으로 char들을 연속으로 출력하는 것이 속 편하다. 

 

5. 문제 하단을 보면 스택을 쓰면 될 것 같지만 덱을 쓰면 훨씬 간편하게 구현할 수 있다. (스택 쓰면 정답 출력할 때 약간 귀찮음...)

* 덱: deque 이라 쓰며 vector와 유사한데 앞뒤로 push_back과 push_front를 할 수 있다. 이것이 가능한 이유는 메모리 할당 방식 자체가 벡터와 다른데, 벡터처럼 하나의 메모리 블록에 연속해서 할당하는 것이 아닌 여러 개의 메모리 블록에 데이터를 할당하기 때문이다. 그렇기 때문에 맨 앞에 원소를 삽입해도 벡터처럼 모든 원소를 뒤로 한 칸씩 밀어줄 필요가 없다. 

 

 

코드

 

#include <iostream>
#include <string>
#include <vector>
#include <deque>

using namespace std;

int main()
{
    int N, K;
    cin >> N >> K;
    
    //정답은 N에서 K를 뺀 길이를 가진 수가 되어야 함
    int size = N - K;
    
    string strNum;
    cin >> strNum;
    
    deque<char> dq;
    for (unsigned i = 0; strNum.length() > i; i++)
    {
        //지울 수 있는 횟수가 남이 있고 &&
        //덱에 원소가 있으며 &&
        //덱에 저장되어 있는 마지막 숫자보다 i번째 숫자가 크면
        while (K && !dq.empty() && strNum[i] > dq.back())
        {
            //덱의 마지막 원소를 삭제한다.
            dq.pop_back();
            //지울 수 있는 횟수 1번 감소
            K--;
        }
        
        //위 조건에 부합하지 않으면 덱에 원소를 추가한다.
        dq.emplace_back(strNum[i]);
    }
    
    //최종 정답은 N - K 만큼만 출력되도록 한다.
    for (unsigned i = 0; size > i; i++)
        cout << dq[i];
    
    return 0;
}