[C++] 프로그래머스 큰 수 만들기 탐욕법

#include <string>
#include <vector>

using namespace std;

string solve(string n, int maxlength);

string solution(string number, int k) {
    string answer = "";
    vector<vector<int>> nums(10);
    int maxlength = number.size() - k;

    //각 수의 각 위치를 넣는다. 여기서 넣은 개수만큼 그 수의 총개수
    for (int i = 0; i < number.size(); i++)
        nums[number[i] - '0'].push_back(i); //char타입 수를 int형으로 바꾸어 저장

    for (int i = 9; i >= 1; i--)
    {
        for (int j = 0; j < nums[i].size(); j++)
        {
            //현재 위치에서 끝 부분까지의 문자열을 넣어준다.
            string temp = "";
            temp = number.substr(nums[i][j], number.size() - nums[i][j]);

            //현재 위치에서 끝 부분까지의 문자열이 제거 후의 길이보다 긴가.
            if (temp.size() >= maxlength)
            {
                answer = solve(temp, maxlength);
                break;
            }
        }

        if(answer != "") break;
    }

    return answer;
}

string solve(string n, int maxlength)
{
    int i = 1;

    //길이와 같아지면 탈출
    while (n.size() > maxlength)
    {
        //이전 수와 현재 수를 비교하여 현재 수가 더 큰지 확인
        if (i - 1 > 0 && n[i - 1] < n[i])
        {
            n.erase(i - 1, 1);  //현재 수가 더 크면 삭제
            i--;    //현재 수에 맞추어준다.
        }
        else
            i++;

        //길이가 더 길지만 왼쪽의 수들이 다 더 커서 i만 증가했을 때 탈출
        if (n.size() == i)
            n = n.substr(0, maxlength);
    }

    return n;
}

 

풀이

1. 높은 수 먼저 확인 하기 위해서 vector에 1~9의 수와 수의 위치를 저장해준다.

2. 높은 수 먼저 확인을 하고 찾았다면 해당 높은 수에서부터 검사 시작

3. 이전 수와 현재 수를 비교하여 현재 수가 더 크다면 이전 수를 삭제해준다.

4. 모든 수들이 이전 수가 크다면 왼쪽의 수들을 최대 길이만큼 잘라준다.