[프로그래머스 코딩테스트 고득점 Kit / 탐욕법(Greedy)] 큰 수 만들기 (python)

풀이 1 : 조합 (실패)

from itertools import combinations

def solution(number, k):
    numList = list(number)
    data = list(range(0, len(numList)))
    maxNum = 0
    answer = ''

    delete = list(combinations(data, k))

    for row in delete:
        tempList = numList.copy()
        for i in row:
            tempList[i] = ''
            
        tempNum = int(''.join(tempList))
        if maxNum < tempNum:
            maxNum = tempNum

    answer = str(maxNum)
    return answer

 

• 조합으로 삭제 가능한 모든 인덱스 조합을 delete 배열에 저장하고 이중 반복문을 돌면서 가장 큰 숫자를 찾았다.
• 주어진 테스트 케이스는 통과했으나, 제출하면 시간 초과로 실패가 떴다.

 

풀이 2 : stack (성공)

def solution(number, k):
    stack = []
    answer = ''

    for n in number:

        while stack and stack[-1] < n and k != 0:
            stack.pop()
            k -= 1

        if len(stack) < len(number) - k:
            stack.append(n)
    
    answer = ''.join(stack)

    return answer

힌트 참고

• stack(fifo)을 이용해서 문제를 해결했다. stack 안에는 만들 수 있는 가장 큰 수가 최종적으로 들어간다.
• number를 반복문으로 돌면서 stack을 채운다.
• k는 삭제할 수이며 stack에서 pop할 때마다 k를 1씩 빼준다.
• n에 대해 stack 안에 값이 있고, stack의 마지막 값이 n보다 크며 k가 0이 아니라는 조건이 만족한다면 계속 stack을 pop 해준다.
• while문을 빠져나온 뒤, stack의 길이가 만들어져야할 숫자의 길이보다 작을 때 n을 append한다.