[코딩테스트]큰 수 만들기(stack)

문제 풀기

효율적이지 않은 풀이(시간초과)

def deleted(number, k):
    dlist = []
    numbers= list(number)
    n = len(numbers)
    # print(numbers)
    # print(combinations(n,k))
    idxlist = combinations([i for i in range(n)],k)
    # print(idxlist)
    for comb in idxlist:
        filtered = [str(num) for i,num in enumerate(numbers) if i not in set(comb)]
        # print(filtered)
        dlist.append((''.join(filtered)))
    return dlist

stack을 이용한 효율적인 풀이

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

회고 😎

• 모든 경우의 수를 확인해야 된다는 생각으로 접근하여 combination을 쓴 것이 비효율성을 낳았다.
• 핵심은 앞쪽에서부터 확인해서 작은 숫자들을 없애 나가는 것이다. 다시말해, k개를 앞에서부터 없애 나가도(Greedy하게 풀어도) 알고리즘 구현에 무리가 없다.
• "자릿수가 영향이 있는 수의 대소비교"를 할 때 greedy한 방법 및 stack을 복기해서 문제를 풀어 보자. 그것이 중요하다.