[Lv 2] 큰 수 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/42883

프로그래머스

 

k개의 숫자를 제거한 후 나올 수 있는 숫자 조합 중 가장 큰 수를 뽑는 문제이다.

이 문제는 k자리 중 가장 큰 숫자를 뽑아 누적하면 해결할 수 있다.

예시) "1924"  k = 2

maxNum = '1'

maxIdx = 0

0 ~ 2 자리까지 반복하며 최대 숫자를 찾음 -> 9

answer = "9"

 

maxNum = '2'

maxIdx = 2

2 ~ 4자리 까지 반복하며 최대 숫자를 찾음 -> 4

answer = "94"

 

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

string solution(string number, int k) {
    string answer = "";
    
    int numSize = number.size() - k;
    int start = 0;
    for(int i=0; i<numSize; i++) {
        char maxNum = number[start];
        int maxIdx = start;
        for(int j=start; j<=k+i; j++) {
            if(maxNum < number[j]) {
                maxNum = number[j];
                maxIdx = j;
            }
        }
        start = maxIdx + 1;
        answer += maxNum;
    }
    
    return answer;
}