[JS] 큰 수 만들기

 

 

난이도: Lv. 2

정답률: 51%

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

프로그래머스

 

 

알고리즘

주어진 문자열에 있는 숫자들을 차례로 스택에 넣는다. 문자열을 모두 순회했거나 k번만큼 제거했다면 반복문을 멈춘다.

1. (스택의 맨 위에 있는 숫자 < 넣을 숫자) 이면 넣지 않고 스택을 pop() 한다.
2. 위의 경우가 아니라면 스택에 넣는다.

위의 반복문을 실행하고 나면 두 가지 경우가 있다.

1. 덜 제거했는데 문자열을 모두 순회한 경우
2. k번만큼 숫자를 제거한 경우

1. 의 경우 스택에 있는 원소들을 앞에서부터 (number.length - k) 개를 모은 문자열이 정답이다.

2. 의 경우 스택에 있는 원소들을 모두 담고, 아직 순회하지 않은 숫자들을 모두 담으면 정답이다.

 

 

코드

function solution(number, k) {
    let answer = '';
    let removeCount = 0;
    let numberIdx = 0;
    const stack = [];

    while (removeCount < k && numberIdx < number.length) {
        if (stack.length && stack[stack.length - 1] < number[numberIdx]) {
            stack.pop();
            removeCount++;
        } else {
            stack.push(number[numberIdx++]);
        }
    }

    if (removeCount < k) {
        for (let i = 0; i < number.length - k; i++)
            answer += stack[i];
    } else {
        for (let num of stack) { answer += num; }
        answer += number.substring(numberIdx);
    }

    return answer;
}

 

 

주저리

그리디로 분류돼 있길래 어떻게 그리디로 풀지 한참 진짜 한참을 고전했는데 스택으로 푸는 문제였다. 아 뭐  그리디도 틀린 말은 아닌데 그래도 이건 너무 하잖아~~~~~~~~~~~