큰수만들기
Aug 17, 2021
»
문제
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
제한 조건 number는 1자리 이상, 1,000,000자리 이하인 숫자입니다. k는 1 이상 number의 자릿수 미만인 자연수입니다.
코드
// ! 내 코드
function solution(number, k) {
const stack = [];
number.split("").forEach((el) => {
while (k > 0 && stack[stack.length - 1] < el) {
stack.pop();
k--;
}
stack.push(el);
});
stack.splice(stack.length - k, k);
return stack.join("");
}
// ! 풀이코드
function solution(number, k) {
const stack = []; // stack을 담아놓을 배열
let answer = ""; // 정답
// number 배열을 반복
for (let i = 0; i < number.length; i++) {
const el = number[i]; // number의 인자를 변수에 저장
// k가 0보다 크거나 stack의 마지막 인자가 el보다 작다면 계속 반복
while (k > 0 && stack[stack.length - 1] < el) {
stack.pop(); // stack의 마지막 인자를 제거
k--; // k--씩 빼서 while을 멈출수 있게 함
}
stack.push(el); // stack 맨 뒤에 el을 푸쉬
}
stack.splice(stack.length - k, k); // stack길이 - k 번째부터 k개를 삭제
answer = stack.join(""); // 배열을 문자열로 합침
return answer;
}
// ! 입출력 예시
console.log(solution("1924", 2)); // 94
console.log(solution("1231234", 3)); // 3234
console.log(solution("4177252841", 4)); // 775841
수도코드
number에서 k만큼 뺐을때 가장 큰 수를 구하는 문제
스택을 사용해서 풀 수 있습니다
- 스택의 길이가 0이므로 입력 배열의 첫 요소를 스택에 삽입합니다
- 스택에 있는 값과 이번 요소의 대소여부를 비교합니다 스택에 있는 값보다 이번 요소가 더 크다면 스택에 있는 값을 빼고 k값을 1 감소시키며 스택에 남아있는 값이 있는지 다시한번 확인합니다
- 이번 요소가 스택에 있는 값보다 작다면 스택에 집어넣습니다
- 이번 요소가 스택 맨 뒤 값보다 크다면 스택 뒤에 있는 값을 꺼내서 k를 1 감소시키고 스택에 이번 요소를 넣습니다
- k가 0이 되면 끝나므로 k === 0일때의 스택 값을 문자열로 바꿔서 제출하면 됩니다