프로그래머스_Level 2 큰 수 만들기

1. 문제설명

문제: 큰수만들기

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

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

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

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

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

 

2. 제한 조건

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

 

3. 입출력 예

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

 

 

📌나의 풀이

k개의 숫자를 제거한다는 개념을 이해하는데 상당한 시간이 걸렸다.

처음에는 for문을 이용하여 current가 current+1보다 작다면 current를 지우는 방식으로 풀었다.

하지만 이렇게 푼다면 테스트 케이스 10번에서 시간초과가 걸린다. 또 다양한 반례들을 생각했어야했다. 

 

for문을 이용한 방법

function solution(number, k) {
    var len = number.length-k;
    number = number.split('').map((content)=>Number(content));
    for(var i=0; i<number.length; i++){
      	
        if(k<=0)break;

        //number[i]가 number[i+1]보다 작으면 
        //마지막 숫자를 삭제해야할 수 도 있기때문에 number[i+1]이 undefined일 때도
        if((number[i]<number[i+1]|| number[i+1]===undefined)){

            //number[i] 삭제
            number.splice(i,1);
            k-=1;
            i=-1;
        }
    }
    
    return number.join('');
}

for문을 돌면서 number[i]의 값이 다음값(number[i+1])보다 작다면 number[i]를 삭제하는 알고리즘이다. 

일단 이 알고리즘은 테스트케이스 10번에서 시간초과 오류가 난다.

 

테스트케이스 10번은 단순히 엄청난게 긴 숫자이다. 시간 초과 오류를 나게 하지 않기 위해서는 다른 방법으로 접근해야한다. 

 

stack을 이용한 방법

function solution(number, k) {
   const stack = []; //글자들이 저장될 스택
   let answer = '';

   for(let i=0; i<number.length; i++){ //number의 길이만큼 돈다
       const element = number[i];

       //k가 0보다 크면서 
       //element가 stack의 마지막값 보다 크면
       while(k>0 && stack[stack.length-1]<element){
           stack.pop();//마지막 값을 뺸다.
           k--;
       }
       stack.push(element);
   }

   //만약 같은 값이 연속으로 나올때를 위해서 splice사용
   stack.splice(stack.length-k,k);
   answer = stack.join('');
   return answer;
}

시간초과를 해결하기 위해서는 stack을 사용해야했다.

for문을 돌면서 number[i]가 stack에 있는 마지막 값보다 크다면 stack의 가장 마지막 값을 뺸다.

k가 0보다 작거나 같아지거나 number[i]의 값이 stack의 마지막 값보다 작다면 스택에 number[i]를 push한다.

 

stack.splice(stack.length-k,k); 는 예를 들면 number이 '999999999' k가 3 같은 예제 때문에 있는 것이다. 

중복된 값이 여러게라면 모두 stack에 push되기 때문에 splice를 통해 k만큼 제거해야한다.

 

💡배운점

- 다양한 방식으로 문제에 접근하는 방법을 배웠다.

- stack을 사용하여 문제를 해결하는 방법에 대해서 알게되었다

 

 

 

✔ 참고 자료

velog.io/@kimtaeeeny/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%81%B0-%EC%88%98-%EB%A7%8C%EB%93%A4%EA%B8%B0-javascript