[프로그래머스/C++] 큰 수 만들기 풀이

프로그래머스 : 큰 수 만들기

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42883

코딩테스트 연습 - 큰 수 만들기 | 프로그래머스

 

문제 설명

 

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

 

제한 조건

 

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

 

너무 어려운 그리디 알고리즘 ,, 😭😭

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

string solution(string number, int k){
    vector<char> bucket; // 조합하고자 하는 배열
    vector<int> removeAt; // 제거하는 배열
   
    // 주어진 숫자로부터 하나씩 꺼내 모으면서, 모아둔 것 중 지금 등장한 것보다 작은 것들을 빼낸다
    for(const auto letter: number){
        // 현재 조합하고자 하는 배열이 비어있는 경우
        if(bucket.empty()){
            bucket.push_back(letter);
            continue;
        }
        // 현재 숫자들이 추가 될 숫자보다 작은 경우 -> 제거
        while(!bucket.empty() && removeAt.size()!=k && bucket.back()<letter){
            removeAt.push_back(bucket.back());
            bucket.pop_back();
        }
        bucket.push_back(letter);
    }
    
    string answer = removeAt.empty() ? number.substr(0, number.size()-k) : string(bucket.begin(), bucket.end());
    return answer;
}