[Programmers_Python] 큰 수 만들기

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

프로그래머스

내 풀이 방식

처음으로 내가 접근한 방식은 itertools의 combinations 함수를 이용해 가능한 모든 경우를 다 찾고 거기서 최대값을 구하는 방식을 생각했다. 시간 초과가 날 것이라고 예상은 했지만, 역시나 시간 초과가 발생했다.

import itertools

def solution(number, k):
    number_lst = list(map(int, number))
    n = len(number_lst)
    lst = list(itertools.combinations(number_lst,n-k))
    answer = list(sorted(lst, reverse = True)[0])
    answer = list(map(str, answer))
    return ''.join(answer)

옳은 풀이 방식

이것 저것 시도하다가 방법을 찾아내지 못하고, 결국 다른 분들의 풀이 방식을 참고 했다. 다른 분들의 풀이 방식을 보니까 Stack 자료 구조를 사용해 문제를 푼 것으로 보였다.

 

1. 빈 Stack구조를 가지는 리스트 answer를 만든다.

2. answer에 number에 있는 숫자 num들을 넣는다.

    어떤 방식으로??

    2.1 answer에 아무것도 없으면 그냥 숫자를 넣는다.

    2.2 k가 0보다 작으면 남은 숫자들을 다 넣는다.

    2.3 넣으려는 수보다 answer의 마지막 원소가 크면 그 수를 answer에 넣는다.

    위 조건들을 만족하지 않으면 answer에서 뒤 원소들을 위 조건들을 만족할 때까지 하나씩 빼준다.

3. answer의 모든 원소들을 join시키고 return한다.

    3.1 k가 0이 아니면 answer[:len(number)-k]까지만 join해서 return한다. 

 

def solution(number, k):
    answer = []
    
    for num in number:
        while k > 0 and answer and answer[-1] < num:
            answer.pop()
            k -= 1
        answer.append(num)
        # print(answer)
    return ''.join(answer[:len(number)-k])

 

 이 문제에서 핵심 키워드는 Stack 자료 구조, 숫자를 어떤 것을 빼고 넣을 지에 대한 기준, 그리고 예외 케이스이다. 이렇게 세 가지를 생각하고 구현했어야 했는데 세가지 다 고려를 제대로 하지 못하고 풀었던 것 같다.