어떤 숫자에서 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" |
Counter 구조 이용해서 풀이하려고 했습니다. 하지만 해당 방법으로 풀게되면 각 자리수의 합이 최대인 수가 나오지, 가장 큰 수가 아니었습니다.
단일 숫자가 작더라도 맨끝에 있는 1을 지우는 것보다는 맨 앞에 있는 4를 지우는 것이 효율적인 순간이 있습니다. 이 경우에는 단일 우선순위 Counter가 아니라 이중 우선순위 Counter로 풀어야 하지 않나 싶습니다......
function solution(nums, k) {
// [설명] 각 자리수가 몇개나 있는지 계산하여 CounterMap형태로 반환
const counterMap = getCounterMap(nums);
// [설명] 0 부터 한칸씩 숫자를 키워가면서 무엇을 지워야하는지 연산하여, CounterMap형태로 반환
const removeTargetMap = getRemoveTargetMap(counterMap, k);
// [설명] nums에서 하나씩 꺼내서 removeTargetMap에 있는 값을 기준으로 삼아서 무시하거나, stack(string)안에 하나씩 넣고 완성
let stack = '';
for (const numStr of nums) {
const num = +numStr;
const isRemovedTarget = removeTargetMap.has(num);
const removedTargetCount = removeTargetMap.get(num);
const isLastRemovedTarget = removedTargetCount === 0;
if (isRemovedTarget && !isLastRemovedTarget) {
removeTargetMap.set(num, removedTargetCount - 1);
} else {
stack += num;
}
}
return stack;
}
function getCounterMap(nums) {
/**
* Counter는 Dictionary형태의 자료 구조의 일부로 Item의 수를 세는 클래스입니다.
* Java, Python과는 달리 JavaScript에서는 이와같이 수동으로 구현해야 합니다.
*/
const counterMap = new Map();
for (const numStr of nums) {
const num = +numStr;
const hasNum = counterMap.has(num);
if (hasNum) counterMap.set(num, counterMap.get(num) +1);
else counterMap.set(num, 1);
}
return counterMap;
}
function getRemoveTargetMap(counterMap, deleteCount) {
let accDeleteCount = 0;
const removeTargetMap = new Map();
for (let num = 0; num < 10; num ++) {
const hasNum = counterMap.has(num);
if (hasNum) {
const numCount = counterMap.get(num);
const remainingDeleteCount = deleteCount - accDeleteCount;
if (remainingDeleteCount >= numCount) {
accDeleteCount += numCount;
removeTargetMap.set(num, numCount);
} else {
if (accDeleteCount === deleteCount) break;
accDeleteCount += remainingDeleteCount;
removeTargetMap.set(num, remainingDeleteCount);
}
}
}
return removeTargetMap
}Counter 자료구조와 정렬방법 같은데서 나오는 Item의 수를 세는 특성이 이 문제를 푸는데 큰 도움이 되지 않는 것 같아요.
그래서 그냥 반복문 통째로 돌렸는데,,, 시간 초과가 나왔습니다.
아마도 로직에서 배열을 만드는 방식 자체가 문제인 것 같아요.
길이가 최대 1_000_000인 경우 하나씩 지워가면서 만들면 1_000_000 > 1(최악의 경우)까지 전부 배열을 만들어야해요.
일반적으로 splice가 훨씬 성능 열악하긴 하지만, slice 자체도 배열 길이가 길면 느린 것은 똑같기 떄문이지 않을까 싶어요...
function solution(nums, k) {
const numsArr = nums.split('');
let cnt = 0;
while(cnt++ < k) {
for (let idx = 0; idx < numsArr.length - 1 ; idx++) {
const nowVal = numsArr[idx];
const nextVal = numsArr[idx + 1];
if (nowVal < nextVal) {
numsArr.splice(idx, 1);
break;
}
}
}
return numsArr.slice(0, nums.length - k).join('');
}
시간이 한 시간이 넘어가서 해설된 코드를 참고했는데, stack 이나 counter같은 특정 자료구조를 너무 사용하는 것은 지양해야 할 것 같네요.
뭔가 생각이 닫히는 기분이에요. ㅠㅠ
function solution(number, k) {
const lifo = [];
for (const nowNum of number) {
/**
* 1924의 경우,
*
* 1회차 lifo가 아무것도 없으므로 바로 1이 들어갑니다.
*
* 2회차 lifo에 무언가 있으므로, lifo의 끝값인 1과 현재값 9를 비교합니다.
* 신규 값(9)이 더 크기 때문에 lifo의 마지막 값을 지우고 9를 넣어줍니다.
*
* 3회차 lifo에 무언가 있으므로, lifo의 끝값인 9와 2를 비교합니다.
* 신규 값(2)이 더 작기 때문에 lifo의 마지막 값을 유지하고 2를 넣어줍니다.
*
* 4회차 lifo에 무언가 있으므로, lifo 의 끝값인 2와 4를 비교합니다.
* 신규 값(4)이 더 크기 떄문에, lifo의 끝값인 2를 지우고 4를 넣어줍니다.
*/
while(lifo.length > 0 && lifo[lifo.length - 1] < nowNum && k > 0) {
k--;
lifo.pop();
}
lifo.push(nowNum)
}
return lifo.slice(0, number.length - k).join('');
}
