[Greedy] 큰 수 만들기 (프로그래머스, Level2)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42883

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

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

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

제한 조건 & 입출력 예

코드

def solution(number, k):
    answer = ''
    
    number = list(number)       # number 배열을 리스트화
    stack = [number.pop(0)]    # number 배열의 첫 번째 요소를 result에 삽입 (괄호 안에 입력한 번호를 인덱스로 가지는 요소가 pop됨)
    
    for n in number:
        if stack[-1] < n:      # result의 가장 마지막 값이 n보다 작으면
            while stack and stack[-1] < n and k > 0:
                stack.pop()     # 괄호 안에 아무런 숫자 없이 배열을 pop하면 뒤에서부터 값이 삭제됨
                k -= 1
            stack.append(n)        # result 배열의 뒤에서부터 n보다 작은 숫자들을 모두 제거한 후, n 값을 삽입
        elif k == 0 or stack[-1] >= n:
            stack.append(n)        # 바로 n 값을 삽입
    
    if k > 0:   # 아직 k개의 수가 제거되지 않은 경우
        stack = stack[0:-k]       # 뒤에서부터 제거
    answer = ''.join(stack)
            
    
    return answer

실행 결과

• 시간이 오래 걸리는 테스트 케이스들이 간혹 보여 이를 줄일 수 있는 방법을 더 찾아봐야겠다.

참고

코드 및 문제풀이 아이디어
위 블로그에 문제 풀이 아이디어와 슈도 코드, 직접 구현한 코드에 대한 설명이 아주 잘 나타나있다. (나중에 문제 풀이 방법을 잊어버리게 되면 해당 글을 통해 다시 보자!)