[프로그래머스] 큰 수 만들기

[문제]

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

코딩테스트 연습 - 큰 수 만들기

 

 

[풀이]

input으로 숫자 number와 number에서 제외할 숫자의 개수인 k가 주어진다.

number에서 k개의 숫자를 제거하여 만들 수 있는 최댓 값을 구하면 된다.

 

처음에는 DFS를 사용하여 모든 경우에 대해 다 확인해봤는데 생각해보니 number의 길이가 1부터 1,000,000까지이다.

 

그래서 다른 방법을 생각해보니 number의 시작부터 큰 수를 골라 총 number.size()-k의 숫자를 골라서 answer로 return 하면 된다. 

 

1. number의 처음부터 'k+선택된 숫자의 수'까지 중에서 가장 큰 수를 선택한다.

2. 선택한 수의 다음 index부터 'k+선택된 숫자의 수'까지 중에서 가장 큰 수를 선택한다.

위의 과정을 'number.size() - k' 번 반복한다. 

 

예를 들어  number= "1234568"이고 k=3인 경우 

총 4개의 숫자를 선택해야 하므로 , 0~3+0 범위 내에서 가장 큰 수를 택해야 된다. 

범위 내에서 가장 큰 수 4를 택하고 , 4~4+1 범위 내에서 가장 큰 수를 택해야 된다. 

이런 식으로 반복하여 4568이라는 가장 큰 수를 구할 수 있게 된다.

 

 

[코드]

 

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    
    int tmp = number.size()-k;
    int idx =0;
    int tmp_idx=0;
    
    for(int i=0;i<tmp; i++)
    {
        int _max = number[idx]-'0';
        tmp_idx = idx;
        
        for(int j=idx; j<=k+i ; j++)
        {
            if(number[j]-'0' > _max ){
                _max =number[j]-'0'; 
                tmp_idx = j;
            }  
        }
        idx = tmp_idx+1;
        answer += to_string(_max);       
    }
    return answer;
}