큰 수 만들기

출처 : 프로그래머스 https://programmers.co.kr/

프로그래머스

---

 

문제

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

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

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

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

입출력 예
number                  k        return
"1924"                    2       "94"
"1231234"            3       "3234"
"4177252841"    4      "775841"

 

나의 풀이

  처음에는 모든 경우의 수를 모두 구해서 가장 큰 값을 구해야 하는건가? 그럼 재귀 방식으로 돌려야 하나?.. 등등 해결 방법을 생각하는게 쉽지만은 않았다. 그러다가 탐욕 알고리즘을 기준으로 생각을 해보니 앞의 숫자가 뒤의 숫자보다 작다면 삭제, 그게 아니라면 살려두고 그 다음 숫자로 이동해서 비교!를 하고 삭제해야하는 숫자의 개수가 일치할 때까지 이를 반복하면 좋겠다라는 생각이 들었고, 중간에 삭제를 하면 index로 인해서 문제가 될 수 있으니 숫자가 삭제되면 idx를 다시 0으로 재할당하고 다시 처음부터 비교를 시작하면서 숫자를 제거해 나가는 방식을 선택했다.

 

function solution(number, k) {
    var answer = '';
    let temp = number.split('');
    let cnt = 0;
    let idx = 0;

    while(cnt < k){
        if(Number(temp[idx]) < Number(temp[idx + 1])){
            temp.splice(idx, 1);
            cnt++;
            idx = 0;
        } else {
            idx++;
        }
    }
    return answer = temp.join('');
}

 

  근데 여기서 문제가 발생한다 .. 옳바른 정답을 반환하는것은 맞지만 ,,, number가 100만자리 이하인 숫자이기 때문에 삭제할 때마다 반복문을 계속해서 돌리게 되므로,, 시간 복잡도가 크게 증가한다는 것이었다. 효율성 이슈로 인한 해결 방법을 내가 생각해 내지는 못했고, 강사님의 해결 방법을 들었다. 강사님은 stack을 이용하여 스택에 숫자를 하나씩 집어넣고 마지막에 들어간 숫자와 그 다음 숫자를 비교해서 그 다음 숫자가 더 큰 경우에는 pop()으로 제거해주고 반대로 작다면 그대로 push()를 제거해야 하는 숫자 개수와 비교하면서 추가와 삭제를 반복하게 된다. 그리고 마지막 stack에 들어있는 값들을 join('')해서 반환한다.

 

  여기서 주의해야 할 점은 엣지 케이스이다. '98765432' 비교가 이뤄지는 처음 숫자보다 그 다음 숫자가 전부 작은 경우에는 stack에 전부 들어가게 되므로 제거해야 하는 숫자 개수와 일치할 때까지 다시 stack에서 pop()을 해주어야 한다.

 

문제 해결

function solution(number, k) {
    let stack = [];
    let count = 0;

    for(let item of number) {
        while (count < k && stack[stack.length - 1] < item){
            stack.pop();
            count += 1;
        }
        stack.push(item);
    }

    while (count < k) {
        stack.pop();
        count += 1;
    }

    return stack.join('');
}

 

  성능측면에서 한 단계 더 나아진 다는것을 알 수 있다. 아직까지도 문제를 해결할 때 문제 해결 방안을 생각해 내고 어떤 자료구조를 이용해서 문제를 해결하면 좋을지가 바로 바로 떠오르는 수준은 아닌 것 같다. 이를 연습하는 방법은 사실 많은 문제를 접하고 풀기 위해 고민하고 풀어보고 다른 사람의 코드도 많이 접하는 방법 뿐이라는걸 알고 있다! 결론은,,,화이팅이다!! ㅋㅋㅋㅋ