1. 처음 생각한 풀이
Q) 조합 알고리즘을 이용하여 모든 경우의 수를 찾고, 그 중 가장 큰 값을 뽑으면 어떨까?
A) 문제점 : 문제 취지에 맞지 않는다. number는 순서가 정해져있는 수이지만, 조합은 순서를 고려하지 않고 뽑는 경우의 수 이기 때문에 해당값을 만족할 수 없다.
2. 문제 해결 풀이
스택에 값을 넣어주고, 대소비교를 통하여, 스택에서 제거하자!
function solution(number, k) {
var answer = '';
var stack = [];
for(var i =0; i<number.length; i++){
var val = number[i];
//while문을 통하여, 현재 stack에 있는 값들 줓 새로 push되는 값보다 작은 값들을 모두제거
while(k > 0 && stack[stack.length-1] < val){
stack.pop();
k--;
}
stack.push(val);
}
return answer = stack.join('')
}
테스트케이스 12번만 통과가 안됐다. 이유가 뭘까?
위 코드로 종료시
for문 종료후 stack에는 [4,3,2,1]이 존재하고, k=1이다.
즉 k > 0일 경우에 처리를 따로 해주어야 하는데, stack.length-k부터 k개를 제거해주면 된다
function solution(number, k) {
var answer = '';
var stack = [];
for(var i =0; i<number.length; i++){
var val = number[i];
//while문을 통하여, 현재 stack에 있는 값들 줓 새로 push되는 값보다 작은 값들을 모두제거
while(k > 0 && stack[stack.length-1] < val){
stack.pop();
k--;
}
stack.push(val);
}
// k>0일 경우 stack.length-k인덱스부터, k개는 제거해주어야한다.
stack.splice(stack.length-k, k);
return answer = stack.join('')
}
순서가 존재하지 않는 모든 경우의 수를 찾을 때는 조합을 사용하자
순서가 존재하는 모든 경우의 수를 찾을 때는 스택을 사용하자