큰 수 만들기

문제 설명

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

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

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

제한 조건

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

입출력 예

number	k	return
1924	2	94
1231234	3	3234
4177252841	4	775841

#include <string>
#include <vector>
#include<iostream>
using namespace std;

string solution(string number, int k) {
    
    string answer = "";
    int numlen = number.size();
    int left = numlen - k;
    int search = 0;

    
    while(answer.size()!=(numlen-k)){
    int max =-1;
    int maxidx = -1;
    for(int i=search; i<=(numlen-left); i++){
        if(max<number[i]){
            max = number[i];
            maxidx = i;
        }
    }
        answer += number[maxidx];
        search = maxidx+1;
        left--;
    }
    
    return answer;
}

어떤 알고리즘 왜 그 알고리즘을 썼는지?

 

그리디 알고리즘을 썼다. 그리디 알고리즘을 쓰기 위해선 그리디로 최대의 값이 나올 수 있다라는 근거가 있어야 한다. 여기서는 앞의 숫자가 크면 클 수록 숫자가 커지기 때문에 앞에서 부터 가장 큰 수를 고를 수 있도록, 즉 현재 상황에서 최적의 값을 구하면 결국 최대의 숫자가 나온다.