Lv2)JS- 큰 숫자 만들기

문제링크

코딩테스트 연습 - 큰 수 만들기

느낀점

이전에 사용했던 숫자들은 사용하지 않기 때문에 쉽게 문제를 풀 수 있을 것이라고 생각했지만, 이번 문제도 역시 그렇게 쉽게 풀수있는 문제는 아니였다. 

이번 문제의 중요키는  stack으로 생각하는 것이다. 내가 확인한 숫자를 stack에 넣고 다음 숫자가 크면 기존에 있던 숫자를 제거하고 다시 stack에 넣는 방식을 이용하는 것이다.

물론 내가 푼 방식으로 해결이 되지 않아서 다른 분의 풀이를 참고하였다. 문제를 풀다 보면 다 푼 거 같은데 테스트 케이스 12번에서 왜 안풀리지라는 의문점이 드는데 질문하기에서 그 해답을 찾을 수 있었다. 

테스트를 돌릴 때 number를 "1000", K를 1로 하게 되면 1000이라는 숫자가 나오는데 원하는 값은 100이기때문에 이 문제를 해결 할 수 있는 방법을 추가만 하면 해당 문제는 해결이 될 수 있다.

 

내가 푼 방법 (풀지 못함)

function solution(number, k) {
    let answer = [];
    let arr = number.split("");
    let count = arr.length - k;
    for (let i = 0; i < arr.length; i++) {
        let num = arr[i];
        for (let j = i + 1; j < arr.length; j++) {
            num = num + arr[j] + '';
            if (num.length === arr.length - k) {
                answer.push(num);
                num = num.substring(0, num.length - 1);
            }
        }
    }
    let max = Math.max(...answer);
    return max;
}

다른 방법 1.

function solution(number, k) {
    let answer = [];
    for(let i =0;i<number.length;i++){
           let num = number[i];
           while(k>0&&answer[answer.length-1]<num){
            answer.pop();
            k--;
           }
           answer.push(num);
       }
        answer=answer.splice(0,answer.length-k);
       return answer.join("");
}

다른 방법 2.

const solution = (number, k) => {
    const stack = [];
    let count = 0;
    for (let i = 0; i < number.length; i++) {
        const item = number[i]
        // stack이 초기에 비어있으면 push 한다.
        if (stack.length === 0) {
            stack.push(item)
            continue;
        }
        // stack에 쌓인 최근 값이 들어와야할 값보다 크거나 같을때까지 꺼낸다.
        while (stack[stack.length - 1] < item) {
            stack.pop()
            count++
            // 만약 숫자를 빼야할만큼 뺐다면 완성된 값을 반환한다.
            if (count === k) return stack.join("") + number.slice(i, number.length)
            // 스택이 비어있으면 루프를 멈추고 스택에 아이템을 추가한다.
            if (stack.length === 0) break;
        }
        stack.push(item)
    }
    // 만약
    return stack.join("").slice(0, number.length - k + count)
}

 

 

reference

해랑쓰님 블로그