[프로그래머스] 탐욕법(Greedy) - 큰 수 만들기 (JavaScript)
문제 설명
어떤 숫자에서 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" |
풀이
스택을 이용해 풀어보자. 스택 후입선출에 유념하며 문제를 풀어야 한다. 그림을 그리면서 풀면 이해가 더 잘된다.
- 제거할 수 있는 개수는 k개이고 k가 모두 소진되면 더이상 제거할 수 없다.
- 스택은 후입선출이다.
단계
- 스택에 아무 것도 담기지 않았을 경우 or 스택에 있는 숫자보다 넣으려는 숫자가 더 작은 경우 그냥 스택에 담는다.
위 조건에 따라 1이 가장 처음 스택에 담겼을 것.
- 다음 숫자는 9다. 1과 9를 비교했을 때 9가 더 크므로 스택에서 1을 제거하고 9를 담는다.
숫자 1을 제거했으므로 이제 제거 가능 횟수는 1회 남음 (k: 1)
- 다음 숫자는 2다. 9와 2를 비교했을 때 스택에 담긴 9가 더 크므로 2를 9 다음에 넣는다. 제거한 숫자가 없으므로 k는 여전히 1이다.
- 다음에 숫자는 4다. 4와 2를 비교했을 때 4가 더 크므로 스택 맨 뒤에 있는 2를 제거하고 4를 넣는다.
삭제 가능한 개수 모두 소진 (k는 0이 되었다.)
- 스택에 있는 9와 4를 합쳐 문자열로 만들어준다.
코드
const number = "1924";
const k = 2;
function solution (number, k) {
const numArr = number.split(''); // ["1", "9", "2", "4"]
const stack = [];
for (let idx in numArr) {
// 스택에 있는 마지막 숫자가 스택에 넣으려는 숫자보다 작은 경우
// 스택에 있는 마지막 숫자를 꺼내서 제거
while ( stack.length > 0 && stack[stack.length - 1] < numArr[idx] ) {
// console.log(stack[stack.length - 1], numArr[idx])
if (k === 0) {
// 제거할 수 있는 개수가 모두 소진됨 (k=0)
// 더이상 숫자 제거할 수 없음
break;
} else {
stack.pop();
// 숫자 하나가 제거됐을 때
// 제거할 수 있는 개수(k=2)에서 1씩 빼준다.
k--;
}
}
// [while 반복문 조건에 해당하지 않는 경우]
// 스택에 아무것도 안 담겨있거나 or
// 스택에 있는 숫자보다 스택에 넣으려는 숫자가 작거나 같은 경우
// 그냥 스택에 담는다.
stack.push(numArr[idx]);
}
// 넣으려는 숫자가 스택에 있는 숫자보다 작으면
// 그냥 계속 담기므로 출력해야 하는 만큼 잘라서 사용
stack.splice(stack.length - k, k);
// 스택에 담긴 두 숫자를 합쳐 문자열로 만든다.
// ["9", "4"] -> "94"
let answer = stack.join('');
return answer; // "94"
}
solution(number, k);
문제 출처
https://programmers.co.kr/learn/courses/30/lessons/42883
Author And Source
이 문제에 관하여([프로그래머스] 탐욕법(Greedy) - 큰 수 만들기 (JavaScript)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@nemo/greedy-탐욕법-큰수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)