[C++]탐욕법(Greedy) 큰 수 만들기(프로그래머스 2레벨)

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
// 1. 맨앞쪽이 커야댐, k개만 빼야함
 
string solution(string number, int k)
{
    for (int i = 0; i < number.size() - 1; ++i)
    {
        if (number[i] < number[i + 1])
        {
            --k;
            number.erase(i,1);
 
            if (k == 0)
                return number;
 
            i = -1;
        }
    }
 
    return number.substr(0, number.size() - k);
}
 

1. 숫자 순서가 바뀌지 않는 부분에서 그럼 앞에 큰 수만 높으면 되겠다 생각했다. 끝

 

다른 분이 분걸 봤는데 속도차이가 10배 차이가 나서 적었다

#include <string>
#include <vector>
using namespace std;
 
string solution(string number, int k)
{
    string answer = "";
    answer = number.substr(k);
 
    for (int i = k - 1; i >= 0; --i)
    {
        int j = 0;
 
        do {
            if (number[i] >= answer[j])
            {
                char temp = answer[j];
                answer[j] = number[i];
                number[i] = temp;
                j++;
            }
            else
                break;
        } while (true);
    }
 
    return answer;
}