프로그래머스 - 큰 수 만들기(c++, javascript)

문제 설명

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

 

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

 

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

 

제한 조건

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

 

입출력 예

출처

 

풀이

그리디 알고리즘

숫자를 앞에서부터 인접한 숫자끼리 비교해서 앞의 숫자가 더 작으면 문자열에서 제거해나간다.

 

- 예외 상황

마지막 숫자까지 탐색했는데 제거된 문자가 없었다면

마지막 숫자 이전의 숫자들이 모두 같은 경우이다.

이 때는 예외 상황을 추가하여 마지막 숫자와 그 이전 숫자 중에 더 작은 값을 제거한다.

 

c++

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

string solution(string number, int k) {
    string answer = "";
    int cnt=0;
    
    while(cnt != k){
        ++cnt;
        
        for(int i=0; i<number.size()-1; i++){
            if(number[i] < number[i+1]){
                number.erase(i,1);
                break;
            }
            if(i==number.size()-2){
                if(number[i] > number[i+1]){
                    number.erase(i+1,1);
                    break;
                }else{
                    number.erase(0,1);
                }
            }
        }
    }
    
    answer = number;
    return answer;
}

 

javascript

자바스크립트는 c++처럼 풀면 시간초과로 테스트케이스 10번을 통과하지 못한다.

// 테스트케이스 10번에서 시간초과
function solution(number, k) {
    let answer = '';
    let cnt=0;
    
    while(cnt != k){
        ++cnt;
        
        for(let i=0; i<number.length; i++){
            
            
            if(i == number.length - 1){
                if(number[i-1] > number[i]) number = number.slice(0,number.length-1);
                else number = number.slice(1,number.length);
                
                break;
            }
            
            if(number[i] < number[i+1]){
                number = number.slice(0,i) + number.slice(i+1, number.length);
                break;
            }
        }
    }
    
    answer = number;
    return answer;
}

 

고민하다가 좀 찾아봤는데 다른 사람들은 stack을 이용해 푸는 것 같다.

 

javascript - stack을 이용한 풀이

function solution(number, k) {
    let answer = '';
    let cnt = 0;
    let arr = [];
    
    for(let i=0; i<number.length; i++){
    
        while(arr.length != 0){
        
            // 카운트가 끝났으면 루프를 빠져나온다.
            if(cnt == k) break;
            
            // 현재 스택에 있는 값이 비교하는 숫자보다 작다면 제거하고 카운트를 1 증가한다.
            if(arr[arr.length-1] < number[i]){
                ++cnt;
                arr.pop();
            }else break;
        }
        
        // 스택이 비어있다면 다음 숫자를 넣는다.
        arr.push(number[i]);
    }
    
    answer = arr.join("").substr(0, number.length-k);;
    return answer;
}