프로그래머스 큰 수 만들기

2020-10-09

1. 문제 링크

1.1. 프로그래머스 큰수만들기

2. 문제 조건

2.1. 문제 설명

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

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

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

2.2. 제한 조건

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

2.1. 컴퓨팅적 사고

숫자로 주어진 문자열에서 - k만큼의 수 만큼을 선택하여 가장 큰 수를 골라주면된다.
이전에 프로그래머스 소수찾기에서 풀었던 것과 유사하긴 하지만 이것이 더 쉽습니다. DFS를 통하여 number.size() - k 개수만큼 숫자를 선택한다
basement조건은 선택한 개수와 k개의 개수를 제거한 개수와 같을 경우이다.
basement조건에 걸리게 되면 check된 값들만 문자열 결합을 통해서 값을 만들어준다. 그 이후 그 값들을 정수로 변환시켜서 최댓값을 구해준다.
모든 최댓값을 구하게 되었으면 to_string()함수를 이용해서 리턴시켜준다.

2.2. 풀이

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int check[1000001];
int max_num= 0;
vector<int> v;
void dfs(string number,int cnt, int len, int k){
    if(len == cnt){
        string str = "";
        for(int i=0; i<number.size(); i++){
            if(check[i]){
                str += number[i];
            }
        }
        int res = atoi(str.c_str());
        // v.push_back(atoi(str.c_str()));
        if(res > max_num){
            max_num = res;
        }
        return;
    }
    if(cnt > len){
        return;
    }
    
    for(int i=0; i<number.size(); i++){
        if(check[i]){
            continue;
        }
        check[i] = 1;
        dfs(number, cnt+1, len, k);
        check[i] = 0;
    }
}
  
    
string solution(string number, int k) {
    int len = number.size() - k;
    int ans = 0;
    dfs(number,0, len , k);
    
    
    return to_string(max_num);
}

AlgorithmProgrammers