꒰ྀི 05. 프로그래머스:: 큰 수 만들기

문제 설명

 

number에서 k개의 수를 제거해 만들 수 있는 가장 큰 숫자 찾기

예를 들어, 1924에서 2개를 제거하면 94가 가장 큼.

 

자료 구조

 

가장 큰 숫자를 찾아야하기 때문에

모든 방법에서 더 큰 수로 이동해야 함.

 

따라서, 탐욕법을 이용해 매 단계마다 가장 좋아보이는 선택을 함.

숫자를 왼쪽부터 살펴보며, 가장 큰 숫자가 되도록 선택함.

 

문제 해결 과정

 

1. 빈 스택을 만들고 제거할 숫자 k를 설정

 

2. 주어진 수를 왼쪽부터 한 자리씩 탐색하고, 제거함.

 

3. 모든 숫자를 탐색하고, 스택에 남은 가장 큰 숫자 형성

 

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

    for (let i = 0; i < number.length; i++) {
        const currentDigit = number[i];
        while (removeCount > 0 && stack.length > 0 && stack[stack.length - 1] < currentDigit) {
            stack.pop();
            removeCount--;
        }
        stack.push(currentDigit);
    }

    while (removeCount > 0) {
        stack.pop();
        removeCount--;
    }

    return stack.join('');
}

 

탐욕법을 사용하면 각 단계에서 최적의 선택을 한다.

스택을 사용해 현재 숫자가 이전 숫자보다 큰지 확인하고,

큰 숫자를 유지할 수 있도록 제거한다.

 

탐욕법과 완전 탐색

 

그렇다면 모든 수를 순회하며 가장 최적의 선택을 하는

탐욕법은 완전 탐색에서 한 단계 업그레이드된 알고리즘인가?

탐욕법 역시 모든 경우의 수를 탐색하는가?

 

아니다, 두 알고리즘은 서로 다른 접근 방식을 가지고 있다.

 

완전 탐색
 모든 경의 수를 탐색해 최적의 해 찾기
예) 1234에서 k개의 숫자를 제거하는 경우
  - 가능한 모든 조합 생성
  - 각 조합을 비교해 가장 큰 숫자 선택

 

탐욕법
  현재 상황에서 가장 좋아보이는 선택을 반복함
예) 1234에서 k개의 숫자를 제거하는 경우
 - 매 단계에서 가장 큰 숫자가 되도록 숫자를 선택하고 제거
 - 각 단계에서 최선의 선택

 

특정 조건에서는 최적의 해를 보장할 수 있는 탐욕법을 사용한다.

 

각 숫자를 선택할 때마다 최대한 큰 숫자가 되도록 선택하는 것이

전체적으로 가장 큰 숫자를 만들기 때문이다.