[알고리즘] 프로그래머스 lv2 큰 수 만들기

처음에 접근했던 방법

def solution(number, k):
    front = ''
    back = ''
    if len(set(number)) == 1:
        return number[:len(number)-k]
    if number.count('9') == len(number) - k:
        return '9' * (len(number) - k)

    while k > 0:
        if len(number) == k:
            number = ''
            break

        max_idx = number.find(max(number)) # 가장 큰 수의 인덱스(중복 있으면 앞에거)
        # print('max: ', max_idx)
        if max_idx <= k:
            front += number[max_idx]
            number = number[max_idx+1:]
            k -= max_idx
        else:
            back = number[max_idx:] + back
            number = number[:max_idx]

    return front + number + back

10번 테스트 케이스에서 시간 초과가 났다.
코드를 조금 변경하니 8번에서도 시간 초과가 났다.
애초에 시간이 아슬아슬했다는 이야기.
<질문하기> 의 글들을 살펴보니, max를 쓰면 무조건 시간초과가 난다는 이야기가 있었고
관점을 바꿔서 그리디한 접근으로, 두 수를 비교해서 작은 것을 버리는 식으로 앞에서부터 처리해야한다는 내용을 보았다.

코드에 적용해보자.

정답 코드

from collections import deque

def solution(number, k):
    if len(set(number)) == 1:
        return number[:len(number)-k]

    right = deque(list(number))
    left = deque()

    while k > 0:
        if list(right) == sorted(right, reverse=True):
            right = list(right)
            return ''.join(right[:len(right)-k])

        while len(right) >= 2:
            if k == 0:
                break
            # print(number)
            if right[0] < right[1]:
                k -= 1
                right.popleft()
                if left:
                    right.appendleft(left.pop())

            else:
                left.append(right.popleft())

        right = left + right
        left = deque()

    answer = ''.join(left) + ''.join(right)
    return answer

짜잔 통과.

싱크빅한 다른 사람의 풀이

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

이렇게 짧게 되다니...
컨셉은 위에서 작성한 것처럼 '두 수를 비교해서 앞의 수가 작으면 버린다'로 동일하다.

내가 넣어본 테스트 케이스

number = '1924' # 94
k = 2
number = '1231234' # 3234
k = 3
number = '1122' # 22
k = 2
number = '4177252841' # 775841
k = 4
number = '111' # 11
k = 1
number = '4321' # 43
k = 2
number = '909090' # 9990
k = 2
number = '720378' # 7378
k = 2