[PS/JS] 프로그래머스 - 큰 수 만들기

Pakxe·2023년 5월 3일

JavaScript ps 프로그래머스

PS

목록 보기

12/16

문제

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42883

풀이 과정

k개의 숫자를 제거하여 만들 수 있는 가장 큰 수를 찾아야 한다.
이어지는 수가 아니고 중간중간 뽑을 수 있다는 것을 알고가자.

큰 수를 찾으려면 어떻게 해야할까?

일단 큰 자릿수(ex 10의자리 > 1의자리) 일 수록 중요도가 커진다. 10의 자리가 큰 수면 1의 자리가 크던 말던 아무 상관이 없기 때문이다. 결국 number를 0번부터 쭉 읽어가면서 큰 수를 높은 자리수로 선정하는 것이 중요하다.

'2141'를 예로 들어보자. 2개를 제거할 수 있다고 한다면, 무엇이 큰 수가 될까?
프로그래밍이 아닌 생각으로 본다면 '41'가 제일 큰 수가 될 것 같다.

어떤 과정을 거쳐서 41이 제일 큰 수가 되는 것일까? 아래 4개의 과정을 거쳐서 생각해볼 수 있다.

1번

1번 숫자인 2가 들어온다. 아직 뭐가 없으므로 '2'이다.

2번

2번 숫자인 1이 들어온다. 이때 2보다 1이 더 작으므로 2를 빼고 1을 넣지 않아도 되므로 그대로 '21' 이 된다. (2를 빼고 1을 넣으면 제일 큰 수가 아니게 되므로)

3번

3번 숫자인 4가 들어온다. 이때 4보다 1이 더 작으므로 1을 빼고 4를 넣는다.
이때 남은 제거 횟수가 1줄어든다. 그렇게 만든 수는 24이다.
아직 제거 횟수가 1 남아있고, 뒤에 더 볼 수 있는 수도 남아있다.
그렇다면 원래 있던 2도 제거하고 4를 넣으면 된다.
이제 남은 제거 횟수가 0으로 더이상 제거할 수 없다.

결국 그 순간 만들어진 가장 큰 수의 제일 끝자리(1의 자리)와 현재 들어오고 싶어하는 숫자의 크기를 비교해서 숫자를 뺄지 말지 결정한다. 이때 어떤 자료구조를 쓸지 감이 오게된다.

이때 중요한 것은 수를 제거할지말지 판단 기준이다.
기준 첫번째로는 남은 제거 횟수, 두번째로는 출력 숫자의 길이이다.

남은 제거 횟수가 0이라면 더이상 제거할 수 없으므로 그대로 종료해 number.length - k 길이로 잘라서 출력하면 되는 것이다.

그리고 출력 숫자의 길이는 반드시 number.length - k개여야한다. 만약 '12345' 가 들어오고 k = 2라고 한다면, '345'가 가장 큰 수가 된다. 이 과정에서 2번째 까지 읽었다면 그 순간 가장 큰 수는 '2'이다. 그런데 그 다음수인 3이 들어오면 2를 제거하고 3을 넣게되는데, 그 다음인 4가 들어오면 또 3을 제거하고 4를 넣게된다. 이렇게되면 최소한 지켜야하는 길이인 number.length - k를 준수하지 못하는 상황이 된다. 따라서 제거를 계속 하되, 최소 길이만 남았다면 그때는 제거를 중지하고 남은 숫자 그대로인 '345'를 출력하면 되는 것이다.

4번

4번 숫자인 1이 들어온다. 남은 제거 횟수가 0이므로 더이상 제거할 수 없을 뿐더러, 4보다 1이 작으니 원래 있던 수인 4에 1을 더해서 '41'이 최종 결과가 된다.

어떤 자료구조를 쓰면 될까?

위 과정을 잘 읽어봤다면, 스택을 써서 풀 수 있단 것을 이해할 수 있다. 결국에 순서에 맞게 숫자를 쌓고, 뽑아내고, 제일 위(마지막)숫자와 비교하는 것이 필요하기 때문이다.

수도 코드

- for 문으로 모든 number를 돈다.
	- while로 제거횟수가 남아있고, 스택 top이 들어오려는 수보다 작을때 반복
    	- if 스택의 길이가 0이면 더이상 pop할 수 없으므로 break
        - else 제거횟수 차감, 스택 pop (작은 수를 제거하고 큰 수를 넣기위함)
   	- 스택에 현재 수를 push (이렇게 하면 현재까지 만들 수 있는 가장 큰 수가 된다)
- return 스택에 남아있는 수를 출력 길이인 number.length - k개만큼 잘라서 반환

정답 코드

function solution(number, k) {
    const stack = [];
    let deleteCount = 0;
    stack.push(number[0]);
    
    for(let i = 1; i < number.length; i++) {
        while(deleteCount < k && stack[stack.length - 1] < number[i]) {
            if(stack.length === 0) break; // 스택 길이가 0이면 pop 불가능이므로 while 종료
            
          	// 스택의 top을 제거하고 남은 제거 횟수를 +1
            deleteCount++;
            stack.pop();
        }
      	
        stack.push(number[i]); // 현재 수보다 작은 수들을 다 제거했으니 현재 수를 push
    }
    
    return stack.join('').slice(0, number.length - k); // 출력 길이만큼 잘라서 반환
}