1. 문제 설명

큰 수 만들기

2. 문제 분석

가능한 만큼(k개) 가장 큰 숫자 앞까지 자른다. 자를 경우 1개씩 k를 감소시켜준다. 구한 가장 큰 자리 수를 다른 곳에 담아두고, 그 이후부터 다시 k가 없을 때까지 반복한다. 12번 케이스에서 런타임 에러가 아지 않으려먼 일단 답을 구하고 정확히 자른 자리수까지 넣어 주어야 한다.

3. 나의 풀이

1. 스택 X : 테스트 케이스 10번 실패

def solution(number, k):
    number = [int(x) for x in number]
    result = []
    length = len(number)

    while k and number:
        idx = number.index(max(number[:k+1]))
        for _ in range(idx):
            number.pop(0)
            k -= 1
        result.append(number.pop(0))
    result += number
    result = ''.join([str(x) for x in result])
    return result[:length - k]

• 스택을 사용하지 않고 리스트 슬라이싱을 통해 max를 구하고, 그 idx까지 pop, 그 max를 result에 담아둠으로써 해결했다. 위 방법을 똑같이 코드로 작성한 게 밑의 풀이 1번인데, 이 경우 10번을 제외한 테스트 케이스는 해결 가능했지만, 시간 초과였다. 다른 경우를 찾아야 했는데, 스택이 답이라는 질문하기 글을 읽고 새롭게 풀게 되었다.

2. 스택 O

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

• 담아둔 스택이 있고 자를 수 있는 k개 있을 때 지금 들어오고 있는 (즉 지금 입장에서는 맨 앞에 있는) 수와 비교해 local max를 구해 result에 더한다. k가 없다면 나머지 num들은 모두 result에 자동으로 더해진다. 스택을 통해 매우 편리하게 풀 수 있었던 문제로, 10번 케이스는 물론 시간 역시 몇 배는 줄어들었다. 앞의 첫 번째 풀이가 for 문을 여러 번 사용한 반면 이 경우 한 번만 사용하니...