큰 수 만들기

들어가는 말

주어진 string을 가지고 k개의 수를 제거했을 때 최대 값을 리턴하는 문제다. 여기서 주의점은 숫자가 차례대로 나와야 한다는 거다.

기본 아이디어는 있었지만 이를 구현하는데 많은 어려움을 겪은 문제였다.

탐욕법에 분류된 것과 같이 차례대로 지나가면서 가장 큰 수를 뽑아서 answer에 넣으면 된다고 생각했다. 이때 남은 숫자가 총길이 - k보다 작다는 조건을 걸어서 숫자가 주어진 조건보다 작지 않게 한다.

입출력 예 1번을 가지고 푼 경우.

int i=1;
    max = v[0];
    for(i; i<number.length(); i++){
        int current_l = number.length() - (i);
        if(current_l < total_l){
            break;
        }else{
            if(v[i] > max){
                max = v[i];
                idx = i;
            }
        }
    }
    
    total_l -= 1;
    int max_two = v[idx+1];
    for(int j=idx+1; j<number.length(); j++){
        int current_ltwo = number.length() - (j);
        if(current_ltwo < total_l){
            break;
        }else{
            if(v[j] > max_two){
                max_two = v[j];
            }
        }
        
    }

그러나 이를 하나로 묶는 것이 어려웠다. 그래서 다른 블로그를 참고했다. 다른 사람들은 가능한 전체 길이와 필요한 길이를 비교하는 대신 for문의 조건을 주어서 풀었다. 확실히...

코드 설명

변수 total은 return할 숫자의 길이다. idx는 현재 숫자의 위치다.

첫번째 for문은 0부터 total(필요한 숫자의 길이. 더 뒤로가면 숫자의 길이를 체우지 못한다)까지 돌려준다. 이때 최대값을 저장하는 char은 ' ' 로 초가화한다.

두 번째 for문은 현재 위치하는 idx+1이다. 왜냐하면 idx가 가리키고 있는 것의 뒤와 비교를 해서 더 큰 값을 max에 저장해야 하기 때문이다. 여기서는 i번째 이후의 제거할 k만큼까지 돌려준다. 그리고 max와 비교하는데 만일 max보다 크다면 max에 해당하는 수를 넣어주고 idx에다가 j를 넣어서 앞의 작은 부분을 뛰어넘으면 된다.

두 번째 for문이 끝나면 max의 값을 answer에 붙이면 된다.

코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    int total = number.length() - k;
    int idx = -1;
  
    for(int i=0; i<total; i++){
        char max = ' ';
        for(int j=idx+1; j<=k+i; j++){
            if(number[j] > max){
                max = number[j];
                idx = j;
            }
        }
        answer += max;
    }
   
    return answer;
}