[프로그래머스 level2] 큰 수 만들기 | Python, JavaScript

🔒 문제

문제 설명

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

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

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

제한 조건

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

입출력 예

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

 

---

🔓 풀이

🔑 문제 해결 / 코드

• Python

def solution(number, k):
    answer = []
    for i in number:
        while k > 0 and answer and answer[-1] < i:
            answer.pop()
            k -= 1
        answer.append(i)

    return "".join(answer[:len(answer) - k])

• JavaScript

function solution(number, k) {
    const answer = [];
    
    for (const i of number){
        while (k > 0 && answer.length && answer.at(-1) < i){
            k -= 1;
            answer.pop();
        }
        answer.push(i);
    }
    
    return answer.slice(0, answer.length-k).join("");
}

---

🍀 Story

그리디를 연습하기 위해 풀어본 문제인데 다른 풀이를 참고해 설루션을 작성했다.

stack 자료형을 사용하는 메커니즘을 이해하면 나름 쉬운 문제다.

 

 

먼저 빈 배열을 하나 만든다. (answer = [])

 

다음으로 매개변수 number의 원소를 반복하는데 아까 만들었던 빈 배열에 원소를 추가해준다.

 

이때 특정 조건을 충족하는 경우는 answer의 마지막 원소를 빼주는 while 반복문이 있는데,

k가 0보다 크고, answer 배열이 비어있지 않고, answer의 마지막 원소가 비교하려고 하는 number의 현재 원소(i) 보다 작다면 마지막 원소를 pop() 하고 k를 1 빼준다.

 

마지막으로 answer에 남아있는 원소를 join() 함수로 하나의 str으로 만들어주는데 이때 answer의 길이에서 k를 빼서 문제에서 요구하는 길이에 맞는 정답을 return 한다.

---

약간의 부연 설명을 하자면 number의 첫 요소가 i로 들어올 때는 answer이 비어있기 때문에 while 반복문을 타지 않고 바로 answer에 i를 추가하게 된다.

 

다음부터는 answer에 원소가 들어있고 k도 1보다 큰 수이기 때문에 answer에 들어있는 원소가 비교하려는 i보다 작은지 비교한다.

 

작지 않다면 answer에 i를 넣어준다.

 

작다면 answer의 마지막 원소를 빼고 k를 1빼준뒤 다시 비교해본다.

answer의 마지막 원소가 i보다 작지 않을 때까지 and k가 0이 되기 전까지 and answer가 비어있기 전까지 반복을 해주고 더 이상 while 반복문 조건을 충족하지 않는다면 i를 answer에 추가해준다.

 

이 로직을 반복하게 되면 number에서 k만큼 뺀다는 조건을 충족하면서 number의 순서에서 큰 수를 우선적으로 answer에 남겨놓게 된다.

 

마지막으로 number의 수가 뒤로 갈수록 작아지는 구조라면 반복문을 타지 않고 계속 answer에 i를 쌓게 된다.

이러면 k도 0이 되지 않고 남아 있을 텐데(뺀 수가 없다)  이 경우에는 answer를 join으로 합칠 때 뒤에서 k만큼 슬라이싱 해서 숫자를 빼주면 정답이 된다.

 

ex) number = "321"; k = 1; 정답 = "32" 

number의 원소가 다음 인덱스의 원소보다 작은 경우가 없기 때문에 while 반복문을 타지 않고 answer에 "3", "2", "1" 순서대로 쌓이게 된다.

k가 1로 남아있으니 answer에서 뒤에서 1개를 뺀 "3", "2"만 합쳐주는 경우까지 고려하면 정답이 된다.