[JS] 프로그래머스 큰 수 만들기

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/42883

1차 시도

삭제 가능한 구간 [i+1, i+k]에서 자신보다 큰 수가 있으면 삭제

substring(startIdx, endIdx)은 기존 string에 영향을 주지 않고 새로운 string변수를 반환한다. 주의. end구간의 인덱스은 포함되지 않는다.

function solution(number, k) {
    const len = number.length;
    var ans = "";

    for (var i = 0; i < len; i++) {
        const target = number.substring(i + 1, i + 1 + k).split("");
        if (target.some(t => number[i] < t))
            k--;
        else
            ans += number[i];
    }
    return k ? ans.substring(0, ans.length - k) : ans;
}

킄.. 더 욕심을 부려야 한다..
나중에 보니까 split("")이 꽤나 무겁다. 알고리즘에서 왠만하면 쓰지말자.

2차 시도

삭제가능한 k구간 중 최대값을 찾아서 삭제

function solution(number, k) {
    const len = number.length;
    var ans = "";

    for (var i = 0; i < len - k;) {
        const target = number.substring(i, i + 1 + k);
        var max = '0', maxi = 0;
        for (var j = 0; j < target.length; j++)
            if (target[j] > max) {
                max = target[j];
                maxi = j;
            }
        ans += target[maxi];
        k -= maxi;
        i += maxi + 1;
    }
    return ans;
}

큭.. 욕심이 부족했던거냐..

최종 코드

stack 2개를 활용하여 문제를 해결해야 한다.

1. 출력stack의 top이 자기보다 작으면 계속 삭제
2. 삭제stack의 크기가 k보다 작을 때까지
3. 삭제 완료하면 나머지를 모두 출력
4. 삭제stack의 크기가 k보다 작으면 출력 끝에서부터 삭제

function solution(number, k) {
    const st = [], ans = [];
    for (var i = 0; i < number.length; i++) {
        const n = number[i];
        while (n > ans[ans.length - 1] && st.length < k)
            st.push(ans.pop());

        ans.push(n);
        if (st.length === k)
            while (++i < number.length)
                ans.push(number[i])
    }
    while (st.length < k)
        st.push(ans.pop());
    return ans.join('');
}

편안..