[Algorithm] 프로그래머스 - 큰 수 만들기 (그리디)

 

 

 

프로그래머스 문제입니다.

[문제설명]

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

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

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

 

---

[제한사항]

 

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

 

---

[입출력]

---

[문제풀이]

function solution(number, k) {
    /*
        condition 1
        1 digit <= number < 1000000 digit, is not float
    */ 
    if (number.length < 1 || number.length > 1000000 || number%1 > 0 ) return false
    
    /**
        condition2
        1 <= k <= number's digit, is not float
    */
    if (k < 1 || k >= number.length || k%1 > 0 ) return false
    
    let answer = []
    let count = k
    
    Loop1: for (let i = 0; i < number.length; i++) {
        Loop2: while (answer.length !== 0 && count > 0) {
            if (answer[answer.length - 1] < number[i]) {
                answer.pop()
                count--    
            }  else break Loop2
        }
        answer.push(number[i])
    }

    return answer.join("").substr(0, number.length-k);
}

 

Idea: 

- Stack을 사용한다.

- n번째 숫자는 n-1번째 숫자보다 커야한다.

   -> 19 < 95

- 앞에서부터 순차적으로 k개만큼 제거한다.

- 같은 수로 조합된 경우를 고려하여, return전 length-k만큼 문자열을 잘라준다.

   -> number 77777와 k=4

   -> answer: 77777