큰 수 만들기 (Programmers 42883)

🧑‍💻 큰 수 만들기

문제 설명

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

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

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

제한사항

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

👀 입출력 예시

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

🧑‍💻 해결방법

• permutation을 활용하려했으나 2번째 테스트 케이스를 돌려보니 조합의 형식이 아니라 스택이었다.
• stack을 활용해서 풀어야한다는 것을 깨달았다.

🧑‍💻 실패 코드

from itertools import permutations

def solution_fail(number, k):
   number = list(number)
   permu = list(permutations(number, len(number) - k))
   next = []
   an = [None for r in range(len(permu))]

   for i in permu :
       next.append(list(i))

   for i in range(len(next)) :
       chk = "".join(next[i])
       an[i] = chk

   an = list(map(int, an))
   answer = str(max(an))

   return answer

🧑‍💻 코드

def solution(number, k) :
   stack = []

   for i in number :
       while stack and i > stack[-1] :
           if k > 0 :
               stack.pop()
               k -= 1
           else :
               break

       stack.append(i)

   if k > 0 :
       for i in range(k) :
           stack.pop()

   answer = "".join(stack)
   return answer

🧑‍💻 총평

• 오랜만에 풀었더니 어렵게 풀려하는 사고가 다시 생겼다.
• 잊지말자 "Simple is Best"