ㅋㅋㅋ이거 이번에 mysql다루면서 봤던 짤이라 첨부함

📍문제

[프로그래머스] Lv.2 큰 수 만들기

💻나의 풀이(시간초과)

from itertools import combinations

def solution(number, k):
    l = len(number)
    num_combinations = list(combinations(number, l - k))
    num_list = []
    for num in num_combinations:
        num_list.append(''.join(num))

    for num in num_list:
        num = int(num)
    
    answer = str(max(num_list))
    return answer

문제를 처음 보고 l-k개 만큼 조합을 구해주고 거기서 max찍으면 되겠다! 라고 생각 했는데 테케 1, 2를 제외하고 어림도 없이 시간초과가 났다. 조합의 경우 시간복잡도가 O(2^N)이라는 사실.. 상당하기 때문에 조합을 구해야하는 수가 많으면 알고리즘테스트에선 써먹기가 어려운 부분이기도하다😂

해당 문제의 제한 조건은 number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.이기 때문에 단순히 combinations를 이용하면 시간초과가 나는 것이 당연했던 것..! 이를 고려해서 생각해 본 알고리즘은 아래에 쓰도록 하겠다.

💻두번째 풀이(스택 사용, 통과)

• k개를 제외한 숫자들에서 각 자릿수들을 비교해 가며 앞 자리보다 작으면 냅두고, 크면 바꿔주고를 반복하면 되지 않을까?? 라고 생각했다.

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

• 그래서 각 자릿수를 비교해 주면서 그 다음 자릿수의 숫자가 더 높으면, 현재 자릿수 글자를 pop 해주고, 더 큰 숫자를 stack에 append 해준다.
• k개를 제외한 숫자만 필요하니까 while반복문을 돌 때 k가 1씩 줄어들도록 한다.
• 마지막 if문은 k가 0이 아닐 때, 나머지 while문 조건을 만족시키지 못하면 뒤에 따라오는 숫자가 stack에 모두 담겨서 자릿수에 맞지 않는 숫자가 출력될 때 이를 슬라이싱해주는 부분이다.