211111 - 큰 수 만들기

◾ 큰 수 만들기 : 프로그래머스 LEVEL 2

• https://programmers.co.kr/learn/courses/30/lessons/42883?language=python3

문제

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

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

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

---

입력

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

출력

• k 개의 수를 제거했을 때 만들 수 있는 가장 큰 숫자

-입출력 예

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

---

◾ 풀이

1. 규칙

• 탐욕법을 통해 해결할 수 있다.
• 첫 수부터 추가하며 다음 수와 비교한다.
  • 이전 값을 A, 다음 값을 B라고 하면
  • B > A인 경우 A를 제거해간다.(A가 없거나 클 때까지 또는 k > 0 인 경우)
  • B < A인 경우 B를 추가한다.
• 마지막 변수부터 비교해야하기 때문에 LIFO인 Stack이 적합하다.
• 예) '1924', k = 2
  • [1], k = 2
  • [9], k = 1
  • [9, 2], k = 1
  • [9, 4], k = 0
  • 가장 큰 수 : "94"

---

2. 프로그램

1. number의 첫 값부터 Stack에 추가한다.
2. Stack의 마지막 값과 비교한다.
   • 마지막 값보다 현재 값이 크고 k > 0인 경우 : 마지막 값 삭제
3. 현재 값을 Stack에 추가한다.
4. 숫자 제거 후 길이만큼의 값을 반환한다.

# 코드
def solution(number, k):
    answer = []
    # number의 각 값을 answer에 추가
    for num in number:
        # k > 0이상이고 answer[-1] < num 인 경우
        # answer의 마지막 값 삭제
        while k > 0 and answer and answer[-1] < num:
            answer.pop()
            k -= 1
        answer.append(num)
    # k가 0이 아닌 경우
    # 뒤의 값이 작은 값이므로 제거한 후 문자열로 만들어 준다.
    return ''.join(answer[:len(answer) - k])

solution("1924", 2) : '94'
solution("1231234", 3) : '3234'
solution("4177252841", 4) : '775841'