[프로그래머스 문제풀이] 큰수 만들기

프로그래머스의 문제 종류 중 그리디 문제타입으로 되어 있는 연습문제이다.

문제는 위와 같다.

문제를 풀 수 있는 가장 간단한 방법은 순열 조합을 이용하여 가능한 조합의 수를 구하고 조합으로 만들어 낼 수 있는 가장 큰 수를 찾으면 된다.

from itertools import combinations
def solution(number, k):
    c = combinations(list(number), len(number)-k)
    num_list = map(''.join, c)    
    answer = max(num_list)
    return answer

하지만 해당 코드를 이용하여 문제를 풀게 되면 몇 개의 문제 이외에는 시간 초과 오류가 발생한다.

문제의 정의에서 number의 자릿수는 최대 100만 자리로 되어 있음을 알 수 있고, 100만 자리의 문제를 순열조합으로 풀게 되면 해결해야하는 복잡도는 거의 지수적으로 증가함을 예측할 수 있다.

때문에 이 문제를 풀기 위해서는 각 단계에서 최고의 방법을 찾아가는 방식으로 코딩하여야 한다.

대부분의 그리디형 문제들이 그렇듯 코드를 보면 이해하기 쉽지만, 해당 방식으로 풀기위한 발상을 떠올리는 것이 어렵다. 나의 경우에도 다른 사람의 코드를 보고 풀이 방식을 알아낼 수 있었다.

def solution(number, k):
    answer = ""
    stack = []
    for i in number:        
        # print(i)
        # print("K1:", k, stack)            
        while stack and stack[-1] < i and k > 0:
            # print("K2:", k, stack)            
            k -= 1
            stack.pop()                
        stack.append(i)
    #     print("K3:", k, stack)            
    # print(stack)
    answer = "".join(stack[:len(stack)-k])
    return answer

풀이 원리는 아래와 같다.

1. 스택에는 현재에서 가장 높은 수가 저장되어 있다.
2. 루프를 돌며 앞에서부터 한자리씩 숫자를 보고 스택과 비교한다.
3. 스택에 있는 숫자보다 현재 가지고 있는 숫자가 큰 경우 스택에서 데이터를 꺼내고 숫자를 바꾼다.
4. 하지만, 버릴 수 있는 숫자가 남아있지 않은 경우 무시하고 진행한다.
5. 끝까지 진행했을 때 버릴 수 있는 숫자가 남아있는 경우 해당 숫자를 제거하고 정답을 산출해낸다(버릴수 있는 숫자가 남아있는 경우는 뒤의 숫자가 같거나 작은 경우이다.)