[프로그래머스] 큰 수 만들기 | 파이썬

---

문제설명

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

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

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

 

제한사항

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

 

입출력 예

---

문제풀이

• 이 문제는 파이썬으로 풀때는 주어진 사항을 따라서 Combination함수를 이용하면 시간 초과가 난다. 그 이유는 첫번째 제한조건으로 number가 100만 자리 이하이기 때문이다. 그래서 조합을 사용하면 경우의 수가 너무 많아져 시간 초과가 발생한다.
• 그렇기에 스택을 기반으로하여 탐욕법 알고리즘을 적용하여 풀면 시간복잡도가 O(n)으로 풀 수 있다.
• number를 for문으로 각 숫자들에 접근하여 answer 스택에 추가한다. 이때 추가할 숫자가 클수록 앞에 배치되는 것이 가장 이득이기 때문에 숫자를 확인하고 number에서 접근한 숫자가 더 크다면 answer에 담긴 숫자를 제거하고 k값을 줄이는 것을 반복해준다. 그렇게 가장 큰 숫자를 넣어주는 선택을 k값이 0이 될때까지 반복해주고 숫자를 계속 answer에 추가해준다. 그렇게 추가된 숫자는 탐욕법에 의하여 가장 큰수부터 채워졌기 때문에 answer를 모두 반환하거나 뒤에서 k번째 이전까지의 answer를 반환해주면 된다.
• 추가적으로 코드를 더욱 단순화 시킨 풀이법도 많이 있어서 더 찾아보며 배울 수 있었다.

코드 & 설명

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