[프로그래머스] 탐욕법 - 큰 수 만들기 문제 풀이

오늘은 프로그래머스에서 탐욕법 문제 중 "큰 수 만들기" 문제 풀이를 해보겠습니다. 과연 이번 큰 수 만들기 문제는 어떤 알고리즘으로 풀어나갈지 궁금합니다. 수의 조합을 통해 가장 큰 수를 만드는 그런 문제이지 않을까 감히 예상해봅니다.

 

 

프로그래머스 > 탐욕법 > 큰 수 만들기 문제 풀이

 

 

 

♬ 문제 정보

• 문제명: 큰 수 만들기
• 문제 난이도: Level 2
• 문제 푼 사람수: 15909명
• 사용 가능 언어: 12개 (JavaScript 사용)

 

 

 

♬ 문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

 

 

먼저 문제 설명 정리해보겠습니다.

• 주어진 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하기
• Inputs
  • number: 최초 주어진 숫자 (string)
  • k: 주어진 숫자에서 제거할 숫자 개수 (integer)
• Output: 주어진 숫자(number)에서 k개의 만큼 숫자를 제거하였을 때 가장 큰 수

 

 

 

 

♬ 제한 조건

⊙ number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
⊙ k는 1 이상 number의 자릿수 미만인 자연수입니다.

 

 

• 2 ≤ number의 자리 수 ≤ 1,000,000
• 1 ≤ k ＜ number의 자리 수

 

 

 

 

♬ 입출력 예

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

 

 

이번 문제도 입출력 예에 대한 설명이 되어있지 않아 직접 설명하면서 이해를 도와드리겠습니다.

• 예제 #1
  • 문제의 예시와 같습니다.
• 예제 #2
  • 1231234 숫자에서 총 3개를 제거하여 가장 큰 수를 만들어야합니다.
  • 그렇게 만들어진 숫자는 1231, 1232, ..., 3123, 3124, 3234, 1234, ... 등 입니다.
  • 이 때, 가장 큰 수는 3234 입니다.
• 예제 #3
  • 4177252841 숫자에서 총 4개의 숫자를 제거하여 가장 큰 수를 만들어야합니다.
  • 그렇게 만들어진 숫자는 417725, 417752, 417758, ..., 7725854, 772581, ...,  775841, 725284, ... 등 입니다.
  • 이 때, 가장 큰 수는 775841 입니다.

 

 

 

 

♬ 알고리즘 만들기

1. 숫자의 앞에부터 스택에 쌓습니다.
2. 마지막 쌓아진 숫자들이 현재 숫자보다 작은지 확인한다.
3. 현재 숫자보다 작은 마지막 쌓아진 숫자는 제거한다.
4. 1,2,3번을 반복하여 만들어진 스택을 문자열로 만들어 반환한다.

 

 

이 문제의 키포인트는 스택 자료구조를 활용하는 것입니다. 스택을 통해 현재 숫자와 그 전 숫자들의 비교를 하여 제거할 숫자를 찾아내는 것이 주요합니다.

 

 

 

 

♬ 코드 구현

function solution(number, k) {
    let answerStack = [];
    let deleteCount = 0;

    for(let i=0; i<number.length; i++){
        // 2. 마지막 쌓아진 숫자들이 현재 숫자보다 작은지 확인한다.
        while(deleteCount < k && number[i] > answerStack[answerStack.length-1]) {
            // 3. 현재 숫자보다 작은 마지막 쌓아진 숫자는 제거한다.
            answerStack.pop();
            deleteCount++
        }
        // 1. 숫자의 앞에부터 스택에 쌓습니다.
        if(answerStack.length < number.length - k) {
            answerStack.push(number[i]);
        }
    }
    
    // 4. 1,2,3번을 반복하여 만들어진 스택을 문자열로 만들어 반환한다.
    return answerStack.join('')
}

 

 

 

 

♬ 채점 결과

 

 

이 문제는 처음 제한사항을 확인하였을 때, N이 최대 100만으로 효율성 테스트 케이스가 있을 법한 문제라고 생각하였지만 정확성 테스트 케이스만 12개 있었습니다. 위 처럼 정확성 테스트 케이스 12개 모두 통과하여 100점으로 가장 큰 수 문제 풀이를 마치겠습니다.