프로그래머스 - 큰 수 만들기(탐욕법)

문제 설명

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

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

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

제한 조건

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

입출력 예numberkreturn

"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

 

나의 풀이

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

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

*탐욕법 문제를 많이 풀어봐야겠다. 딱히 유형이 정해져있다는 느낌은 못 받았다. 상황에 따라 최고의 조건을 고르는 것이다 보니 최적의 조건을 만드는 과정이 어렵다... 다른 사람의 풀이를 보고 힌트를 얻어 다시 풀어보았고, 코드 구성은 그렇게 어렵진 않다... for문 안에서 while문으로 조건을 맞추는 과정들이 탐욕법에서 많이 보이는데 좀 익숙해져보자!

 

1) 스택 자료구조를 사용하여 (LIFO) 조건에 따라 꺼낼지, 추가할지..!

- 팝 되는 조건: 스택이 비어있지 않아야하고, k(빼지는 문자의 수)가 0이 아니고, 들어가는 수가 스택의 마지막 수보다 크다면, 스택의 마지막 수를 제거! 조건에 만족하다면 계속 반복! 

 

2) while 조건에서 나온다면 스택에 추가하는 과정 

 

3) 이를 number의 수를 하나씩 점검하는 과정

 

4) 리턴할 때, 슬라이싱을 굳이 한번 더 해준 이유는 number가 999이고 k=2라면, 즉, 같은 수가 반복으로 나올 때이다. 리턴은 9가 나와야지만 슬라이싱을 하지 않는다면, 999가 나온다. 따라서 이러한 부분에 대한 예외 처리이다!