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 함수를 완성하세요.
제한 조건
number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
k는 1 이상 number의 자릿수 미만인 자연수입니다.
입출력 예
| number | k |
|---|---|
| "1924" | 2 |
| "1231234" | 3 |
| "4177252841" | 4 |
문제 풀이
function solution(number, k) {
let num = number.split("");
let stack = [];
for (let j = 0; j<num.length; j++) {
while (k > 0 && stack[stack.length - 1] < num[j]) {
stack.pop();
k--;
}
stack.push(num[j])
}
stack.splice(stack.length-k,k)
return stack.join('')
}처음 문제를 풀때는 재귀를 써서 해결해야하는 생각이 들었다. 앞의 숫자가 뒤의 숫자보다 큰 경우는 넘어가고 뒤의 숫자가 큰 경우는 앞의 숫자를 삭제하는 방향으로 문제를 해결하려고 했다. 문제를 풀수록 재귀에 어떤 파라미터를 넣어야할지 고심했고 재귀를 하지 않고 해결할 수 있는 방법이 뭐가 있을까 생각해보다가
프로그래머스 - 큰 수 만들기 (javascript)
다른 분의 풀이법을 보고 스택을 사용해서 풀 수 있다는 것을 깨달았다. k가 0보다 클 때 num[j]가 스택의 마지막 요소보다 크다면 스택의 마지막요소를 삭제하고 k를 1개씩 줄이고 나서 마지막 스택보다 크다면 num[j]를 스택에 넣어준다. 모든 number를 반복해준 뒤 k가 남아있다면 제일 마지막에서 빼 준 뒤 리턴값을 넣어주면 된다.
스택과 큐에 대해서 공부는 했지만 실제로 사용해보려고 한부분에서 어떻게 이용해야할지 감을 잡지 못한 부분이 많았다. 다른 문제를 더 풀어봐야할 것같다.
