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

number	k (제거하려는수)	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

다음문제는 k개를 제거후 가장큰숫자를 구해야하는 문제입니다.

 

제가 생각한 알고리즘은 작은 수를 제거하는 방식이 잘못되었었습니다.

 

const small = new Array(k).fill(Infinity); // 삭제하려는 값을 배열로 관리

for (const num of nums) {
    for (let i = 0; i < k; i++) {
        if (small[i] > num) { // 삭제값 > 숫자
            small[i] = num; // 값 치환
            break;
        }
    }
}

 

• k개의 가장 작은 숫자를 골라 small 배열에 저장한 후 제거하려는 방식.
• 문제는 숫자의 위치(순서)가 중요하다는 것!
  예: 4177252841에서 4와 1이 가장 작다고 해도 무작정 제거하면 안 됩니다.
  앞쪽에서 제거하는 것이 결과에 큰 영향을 미침

 

이문제는 그리디알고리즘을 활용해서 풀면 풀립니다.

즉, 앞에서부터 숫자를 보면서, 앞 숫자가 뒤 숫자보다 작으면 제거해야 가장 큰 숫자가 나옵니다.

 

 

앞자리수가 stack의 가장 아래에있는 값이여서 자리수를 유지하면서 작은값들은 pop으로 stack에서 제거할수있습니다.

결국 stack에 남아있는 값들은 최대값이 됩니다.

 

 

function solution(number, k) {
    const stack = [];
    
    for (let i = 0; i < number.length; i++) {
        const current = number[i];

        while (k > 0 && stack.length > 0 && stack[stack.length - 1] < current) {
            stack.pop();
            k--;
        }

        stack.push(current);
    }

    // 아직 제거할 숫자가 남아 있다면, 뒤에서 제거
    return stack.slice(0, stack.length - k).join('');
}

 

while문을 사용해서 stack을 연속으로 제거하는 이유는 왜일까요?

 

맨앞자리의 가장큰수를 만족하는 이유이기때문입니다.

그렇지만 최대 k개까지 제거를 감안하여 k값을 pop할때 -로 관리해줍니다.

 

 

특정 문자열에서 최대값을 만드는 문제에 그리디 알고리즘을 적용한 사례입니다.
항상 최적의 결과를 기대하며, 그리디 알고리즘을 스택에 접목해 구현한 예시입니다.

 

k 값과 while 조건의 세부 조절이 필요하긴 하지만,
전체 숫자를 한 번만 순회하는 단일 for문으로 구현되어 시간복잡도는 O(N)이며,
스택을 활용해 숫자 관리가 매우 깔끔해집니다.

이 과정을 통해 그리디 알고리즘의 효율적이고 혁신적인 문제 해결 방식을 깨닫는 좋은 경험이었습니다.