프로그래머스 [level2] 큰수 만들기- 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의 자릿수 미만인 자연수입니다.

  입출력 예

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

코드

from collections import deque

def solution(number, k):
    answer = deque()  # answer 구할 리스트
    text = ''

    for i in number:
        if len(answer) == 0:
            answer.append(i)
        else:
            while (answer and i > answer[-1] and k != 0):
                answer.pop()
                k -= 1
            answer.append(i)
    for i in answer:
        text += i
    if k != 0:  # k 나머지 값 정리하기
        text = text[0:len(text) - k]

    return text

풀이설명

로직 자체를 생각하는데 살짝 시간이 걸렸었다. Number에서 숫자를 하나하나씩 가져오면서 처음 빼온 숫자면 바로 추가하고

그다음 부턴 숫자의 대소비교가 진행된다. 숫자를 비교하면서 뺀 숫자가 큰 숫자이면 answer에 담긴 숫자를 빼고 k를 -1씩 진행하면서

answer를 정리해준다. 

처음엔 위의 로직을 바탕으로 진행했을 때 테스트케이스는 다통과했지만 실제 코드에서 유형 한개를 풀지 못해서 또 고민해봤다.

그랬더니 

1. 입력: "654321" , k = 1 // 결과: "65432"
2. 입력: "654321", k = 5 // 결과: "6"

의 결과일 때의 반례를 찾아서 k가 0이 아니고 나머지 숫자가 남을경우 answer로 만든 text를 다시 정리하면서 진행했더니 풀렸다.