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

문제 설명

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

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

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

 

제한 조건

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

 

풀이

number를 순회하며 넣으려는 값과 이전 값을 비교하며, 제거해야 할 숫자 수가 남은 경우를 고려하며 문제를 해결하였다.

만약 number의 원소 i가 반복문을 순회하며

1. 당시 조건에 만족한 값의 리스트의 마지막 인덱스보다 크고
2. k > 0이고
3. 당시 조건에 만족한 값의 리스트가 빈 리스트가 아니라면

해당 조건을 반복하며 기존에 들어있는 값을 제거하고, k의 값을 -1한 후 원소 i를 조건에 만족한 값의 리스트에 담는 방식으로 진행하는 코드를 작성하였다.

추가적으로, 해당 반복을 모두 진행했지만 k가 아직 0이 아니라면, 더 제거를 해야하는 경우도 생각해야한다.

앞에서 진행한 조건에 '당시 조건에 만족한 값의 리스트의 마지막 인덱스보다 크고'라는 조건이 있기에, 최종적으로 완성된 리스트를 리턴할 경우 리스트 전체가 아닌 (리스트의 길이 - k)까지의 원소를 리턴하게 하면 해결된다.

 

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