문제
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
- 제한 조건
- number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
- k는 1 이상
number의 자릿수
미만인 자연수입니다.
풀이
1차 풀이
function solution(number, k) {
let answer = [];
number = number.split('');
function permutation(arr, selectNum) {
let result = [];
if(selectNum === 1) return arr.map(v => [v]);
arr.forEach((v, idx, arr) => {
let fixed = v;
let restArr = arr.filter((v,index) => index !== idx);
let permutationArr = permutation(restArr, selectNum -1);
let combineArr = permutationArr.map(v => [fixed, ...v]);
result.push(...combineArr);
});
return result;
}
// answer = permutation(number, number.length - k)
answer = permutation(number, number.length - k).map(v => +v.join(''));
// return Math.max(null, answer)
return Math.max.apply(null, answer);
}
문제를 제대로 이해하고 못하고 풀었기에 문제가 생겼다.
일단 숫자를 제외하고 남은 수를 얻는 과정을 잘못 이해했다.
제외하고 순서대로 보는 것이 아닌, 숫자를 number.length - k 개를 뽑는 순열과 같다고 이해했다.
그래서 순열을 구하고 그 중에서 최대값을 구한 것이다.
결과는 역시 통과하지 못했고, 시간 제한에도 걸렸다.
n이 1,000,000자리 숫자 미만이기 때문에 순열을 구하면 절대 효율적이지 못하다.
모범 답안
function solution(number, k) {
const stack = []; // 남은 숫자들이 저장될 스택
for (let i = 0; i < number.length; i++) {
let el = number[i]; // 현재 요소
// 제거가능한 숫자 남아있음 && el이 스택 맨 위보다 클 때
while(k > 0 && el > stack[stack.length-1]) {
stack.pop(); // 맨 위 숫자 꺼냄
k--; // 제거 숫자 하나 줄어듬
}
stack.push(el);
}
return stack.slice(0, number.length - k).join('');
}
- 첫번째 요소는 비교대상이 없기 때문에 (
stack[stack.length -1]
= undefined 라서 for문 통과함) 무조건 stack에 추가된다.
- 그 다음 값은 stack의 top 요소와 비교해서 작으면 stack에 추가되고, 크다면 stack에 있던 수를 빼고 추가된다.
여기서 빠진 수가 제외된 숫자가 되는 것이다. 이 과정에서 제외 가능한 숫자인 k도 하나 줄어든다.
- 맨 마지막 숫자까지 for문을 통과해도 k가 0이 아닌 경우가 있기 때문에 이를 처리해야한다.
바로 '7777777' 같이 각 자릿수가 같아서 비교가 불가한 경우가 대표적이다.
위 숫자가 for문을 거친다면stack
= '7777777' /k
= 4 가 된다.
그러므로 k 만큼 뒤에서 요소를 제외한 배열을 만든다.
- stack을 문자열로 바꿔 반환한다.
정확도 테스트 결과
참고
'Coding test' 카테고리의 다른 글
[프로그래머스] 기능개발 (Lv.2) - javascript (0) | 2022.05.11 |
---|---|
[프로그래머스] 구명보트 (Lv.2) - javascript (0) | 2022.05.11 |
[프로그래머스] 소수찾기 (Level 2) - javascript (0) | 2022.05.07 |
[프로그래머스] 카펫 (Level 2) - javescript (0) | 2022.05.06 |
[이것이코딩테스트다] 그리디 : 실전문제 - javascript (0) | 2022.05.04 |