[코테] 큰 수 만들기

프로그래머스 level 2

아이디어

1. 주어진 숫자 중 k개로 만들 수 있는 숫자 리스트를 구하기
2. 그 중 max 값 찾기

1번은 결국 len(number) - k 개로 만들 수 있는 숫자들의 리스트라고 생각했고 combinations 을 써서 풀면 되는 문제라고 생각했다!

구현 코드 (시간 초과)

from itertools import combinations

def solution(number, k):
    num_list = []
    num_string = ''
    number = list(number)
    permu_list = list(combinations(number,len(number)-k))
    for i in permu_list:
        for j in i:
            num_string += str(j)
        num_list.append(int(num_string))
        num_string = ''
    
    return str(max(num_list))

이렇게 풀어서 제출하니 시간초과가 떴다 ...

다른 접근 방법이 생각이 안 나서 구글링을 해보니 stack을 이용해서 풀 수 있는 문제였다.
큰 수를 만든다는 게 결국 앞에 수가 큰 게 큰 수가 되기 때문에 그런 성질을 이용해서 LILO을 사용해서 stack에 가장 큰 수를 남기면 되는 그런 문제였다!다!

다시 구현한 코드 (stack 사용)

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

comment

자료 구조를 더 공부하고 문제 풀 때 어떤 자료 구조를 사용하면 좋을지에 대한 생각을 하는 습관을 들여야겠다.