[프로그래머스] Lv2. 큰 수 만들기

큰 수 만들기

문제 설명

어떤 숫자에서 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):
    number = list(number)
    
    max_n = max(number[:k])
    idx = number.index(max_n)
    number = number[idx:]
    k -= idx
    
    sorted_li = sorted(number, reverse = True)
    for i in range(k):
        m = sorted_li.pop()
        number.remove(m)
    return ''.join(number)

• k자리 안에 가장 큰 맨 앞자리를 찾아 그만큼의 k를 빼서 k 값을 갱신
• 남은 number 중에서 가장 작은 값을 빨리 찾기 위해 내림차순 정리 후 pop()으로 m에 저장
• m을 number에서 제거

이 풀이는 테스트3의 경우를 통과하지 못했다..

 

정답 풀이

def solution(number, k):
    answer = [] 
    
    for num in number:
        while k > 0 and answer and answer[-1] < num:
            answer.pop()
            k -= 1
        answer.append(num)
    if k:
        answer = answer[:len(answer) - k]
    return ''.join(answer)

• Greedy 방식으로 가장 큰 수를 만들기
  • 큰 숫자가 앞에 올수록 더 큰 수가 되므로, 작은 숫자는 가능한 한 빨리 제거하는 전략을 사용한다.
• 반복문을 통한 처리
  • for num in number: 주어진 숫자를 왼쪽에서부터 차례로 처리한다.
  • while 문을 사용하여 현재 숫자가 앞서 있는 숫자들보다 크면, 앞의 숫자를 제거하고 새로운 숫자를 추가한다. 이때 k > 0인 경우에만 제거할 수 있다.
• 남은 k 처리
  • 숫자 문자열을 다 처리한 후에도 k가 남아 있다면, answer 리스트에서 남은 숫자들을 뒤에서부터 제거한다.