[프로그래머스] 레벨 2 - 큰 수 만들기

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

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

그리디 유형의 레벨 2 문제다.

맨 처음에 조건을 잘못 읽어서 맨 큰 숫자부터 하나씩 뽑아서 배치해 리턴하는 문제인 줄 알았으나,

"주어진 문자열의 순서를 바꾸지 않고 k개 만큼 지워서 만들 수 있는 가장 큰 수를 리턴"

하는 문제였다.

 

이 문제를 풀기 위해서는 자릿수에 대한 개념이 필요하다.

가령, 8자리 number 문자열이 주어지고, k가 3으로 주어진 경우, 총 5자리의 숫자를 만들어야 한다.

문자열의 순서를 바꾸지 않고 맨 처음 자릿수를 만들 때는 첫 번째 숫자부터 끝에서 5번째 자리의 수까지 고려할 수 있다. 왜냐하면 맨 뒤 네 자리는 그 이후의 숫자를 위해 사용할 수 없기 때문이다.

 

그래서 처음에 얼마나 긴 문자열을 만들어야 하는지 확인한 뒤 이를 'required_len'에 집어넣고

[0] ~ [required_len] 까지 검사, required_len--;

[0] ~ [required_len] 까지 검사, required_len--; 를 반복하다가

required_len이 1이 될 때까지 이를 반복한다.

 

그 결과 총 required_len 길이의 가장 큰 문자열이 완성된다.

vector<int>를 사용한 이유는 문자열의 문자 아스키 값 그대로 넣고 이를 문자열에 넣어줄 때 바로 붙일 수 있게 하기 위함이다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
 
string solution(string number, int k) {
    string answer = "";
    int required_len = number.length()-k;
    vector<int> tmp;
    while(required_len > 0){
        int maxval = 0;
        int maxidx = 0;
        for(int i=0; i <= number.length() - required_len; i++){
            if(maxval < number[i]){
                maxval = number[i];
                maxidx = i;
            }
        }
        tmp.push_back(maxval);
        number.replace(0, maxidx+1, " ");
        required_len--;        
    }    
    for(int i=0; i<tmp.size(); i++) answer += tmp[i];
    return answer;
}