[프로그래머스] 탐욕법(Greedy) - 큰 수 만들기

문제

문제 설명

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

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

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

제한 사항

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

입출력 예

풀이

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

    for num in number[1:]:
        # stack 제거 조건과 k 조건 하에서 스택에 담긴 이전의 수 중 현재 수보다 작은 수를 제거해나감
        while len(stack) > 0 and num > stack[-1] and k > 0:
            stack.pop()
            k -= 1
        stack.append(num)  # number의 모든 숫자를 stack에 넣어 비교 대상이 되도록 함

    # k개만큼 제거되지 않았을 경우 남은 수만큼을 뒤에서 제거
    if k > 0 :
        stack = stack[:-k]
    
    answer = ''.join(stack)

    return answer

💡

• 스택을 이용한 방식
• 다 제거되지 않았을 경우를 위한 처리를 해줘야 함.
• 이런 문제 이전에도 풀었는데 또 틀린거보고 다음에는 무조건 맞추기 위해 정답 풀이를 기록합니다,,

번외 - 효율성에서 빠꾸먹은 풀이

def solution(number, k):
    answer = ''
    result = list(number)

    while True:
        for i in range(1, len(result)):
            if result[i-1] < result[i]:
                del result[i-1]
                k -= 1
                break
        if k == 0:
            break
    
    answer = ''.join(result)
    return answer

😅

• 최초 문자열을 앞에서부터 검사하며 문자 자신이 다음 문자보다 작을 경우 제거한 뒤 이렇게 바뀐 문자열을 최초 문자열에 대치시킴. k개의 문자가 제거될 때까지 위 과정을 반복.
• 테케 10번, 12번에서 시간초과 뜸 휴
• 한 바퀴 돌때 한 문자씩만 제거하고, 문자열을 대치시킴으로써 이미 검사하여 통과한 문자까지 다시 크기 검사를 하게되므로 불필요한 검사 과정이 반복되어 시간을 잡아먹는 것 같음.
• 위 풀이의 치명적인 한계!! number = "987654321", k = 8과 같은 경우에는 while문을 빠져나오지 못해 무한루프에 빠짐;