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

문제를 정리해보자.

 

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

예) 1924에서 2개를 제거하면 19, 12, 14, 92, 94, 24이다. 여기서 가장 큰 수는 94이다.

 

 

풀이를 생각해보자.

 

'가장 큰 수'를 만들려면 어떻게 해야 할까?

앞자리에 큰 수가 있어야 한다.

따라서 k개만큼 제거하되 앞자리일수록 큰 수가 와야 한다.

 

1) 1924를 예로 들어보자. (k = 2)

 

9는 1보다 크다. 따라서 1보다 앞에 위치해야 한다. 따라서 1을 제거하고 9를 앞에 위치시킨다.

이제 제거할 수 있는 수는 1개이다. (결과 : 924)

 

4는 2보다 크다. 따라서 2보다 앞에 위치해야 한다. 따라서 2를 제거하고 4를 앞에 위치시킨다.

이제 제거할 수 있는 수는 0개이다. (최종 결과 : 94)

 

 

2) 4177252841을 예로 들어보자. (k = 4)

 

7은 1보다 크다. 따라서 1보다 앞에 위치해야 한다. 따라서 1을 제거하고 7을 앞에 위치시킨다.

이제 제거할 수 있는 수는 3개이다. (결과 : 477252841)

 

7은 4보다 크다. 따라서 4보다 앞에 위치해야 한다. 따라서 4를 제거하고 7을 앞에 위치시킨다.

이제 제거할 수 있는 수는 2개이다. (결과 : 77252841)

 

5는 2보다 크다. 따라서 2보다 앞에 위치해야 한다. 따라서 2를 제거하고 5를 앞에 위치시킨다.

이제 제거할 수 있는 수는 1개이다. (결과 : 7752841)

 

8은 2보다 크다. 따라서 2보다 앞에 위치해야 한다. 따라서 2를 제거하고 8을 앞에 위치시킨다.

이제 제거할 수 있는 수는 0개이다. (최종 결과 : 775841)

 

 

3) 만약 최종 결과가 반환해야 하는 길이 보다 길다면?

예를 들어 9999 (k = 1)이라면 최종 결과가 9999가 된다. 왜냐하면 값이 같은 수는 제거되지 않기 때문이다.

따라서 k개 수만큼 제거되지 않을 수 있다.

 

최종 결과에서 제거하지 못한 수만큼 제거하면 된다.

 

 

구현해보자.

 

 

def solution(number, k):
    stack = []
    l = len(number) - k

    for num in number:
        while stack and k > 0 and stack[-1] < num:
            stack.pop()
            k -= 1

        stack.append(num)

    answer = ''
    for i in range(l):
        answer += stack[i]

    return answer


print(solution("4177252841", 4))

 

 

stack 구조를 이용했다. 시간복잡도는 O(n)이다.

 

 

처음 시도에는 백트래킹을 이용했다.

k개를 제거한 모든 경우의 수를 찾고 최대값을 찾았다.

당연히 O(n^2)으로 시간초과이다. 

 

def back(cnt, n, k, li, dp, number, answer):
    if cnt == k:
        tmp = ''

        for num in li:
            tmp += str(num[1])

        answer = max(answer, int(tmp))
        return answer

    for i in range(n):
        if dp[i] == 1 or (li and i < li[-1][0]):
            continue

        li.append((i, number[i]))
        dp[i] = 1

        answer = back(cnt + 1, n, k, li, dp, number, answer)

        dp[li[-1][0]] = 0
        li.pop()

    return answer


def solution(number, k):
    n = len(number)
    k = n - k

    li = []
    dp = [0] * n

    number = [int(num) for num in number]

    answer = 0

    answer = back(0, n, k, li, dp, number, answer)

    return str(answer)


print(solution("4177252841", 3))