[ Lv 2 ] 큰 수 만들기

- 처음에는 그냥 구간 나누어서 구간의 최댓값으로 맨 앞자리부터 채우는 방식으로 구현하였음.

- 10번에서 무한정 시간초과가 나서 잘 안되어서 다른 방식으로 구현.

- 다음은 잘 안됬던 소스

def get_max(number, src, dest):
    num = number[src]
    idx = src
    for i in range(src, dest):
        if num < number[i]:
            num = number[i]
            idx = i
        if number[i] == 9:
            break
    
    return (num, idx+1)

def solution(number, k):
    length = len(number)
    nex = 0
    c = length-k
    answer = ''
    
    while True:
        m, nex = get_max(number,nex,length-c+1)
        answer += m
        if len(answer) == length-k:
            break
        c = c - 1
        
    return answer
    from collections import deque

---

- 개수가 최대 100만개라 그런거 같았음. 따라서 풀이 방식을 스택으로 그리디하게 구현

- 매 순간 스택에 넣을때 스택 맨 위 요소가 넣으려는 요소보다 작다면 계속 빼주다가 맨 위 요소가 더 커지면 그때 넣어줌, 단 빼줄 때 몇개 빼주었는지 카운팅 해주어야 함. 최대 k개 빼야 하므로.

- 번외로 k개를 빼지 못하였다면 마지막에 맨 뒤에서 k개 빼줌

def solution(number, k):
    stack = deque()
    delcnt = 0
    for i, n in enumerate(number):
        while stack and delcnt != k:
            if stack[-1] < n:
                delcnt += 1
                stack.pop()
            else:
                break
        stack.append(n)
    
    answer = "".join(stack)
    if delcnt < k: # 충분히 지우지 못한 경우 뒤에서부터 지워줌.
        answer = answer[:-(k-delcnt)]
        
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges