[Programmers] 큰 수 만들기

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

number에서 k개를 '빼는'문제이다.
나는 빼기보단 남은 수들을 뽑는 것에 초점을 맞춰서 문제를 풀었다.

이번에도 순열과 조합을 이용했는데 결과는 처참히 실패!

from itertools import combinations

def solution(number, k):
    number = list(map(str, number))
    l = set(combinations(number, len(number)-k))
    t = []
    for i in l:
        t.append(''.join(i))
    return str(max(t))

combination을 이용하여 모든 경우의 수들을 뽑고, 그 수에서 가장 큰 것을 return 해주는 함수를 만들었다.

그러나 for문을 하나만 사용했는데도 불구하고 시간초과가 나왔다.
그래서 문제를 다시 읽어보고 다시 고민했다. 그래도 답이 안나와서 구글링을 했다.

'뽑는다'라고 했으니, number를 처음부터 끝까지 돌면서 뽑은 수보다 작으면 안뽑으면 되는 것이었다!

생각보다 정말 단순해서 .... 허무했다 ㅎ

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

stack을 사용하여 풀었다.

만약 스택의 마지막 값보다 리스트의 첫번째 값이 크면 마지막 값 순서대로 제거한다.
제거되지 않은 수가 있다면 남은 부분은 삭제해준다.
greedy 알고리즘을 이용했다고 하는데 역시 알고리즘은.. 끝도 없다...

더 연습해야지