99클럽 - 큰 수 만들기

프로그래머스

아이디어

단순해 보이지만 거슬리는 조건이 몇 가지 있다.

• 문제 조건 상 정렬 순서는 유지 돼야한다.
• number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.

입력이 100만으로 매우 무거운 계산이 예상되기 때문에 경우의 수를 전부 비교할 수 없다.
어떤 값이 작은 값인지 확인하기 위해 정렬을 사용 할 수 없다. 이는 숫자 각각의 크기외에 자릿수 라는 다른 변수가 있기 때문이다.

기본적으로는 앞에서부터 순서대로 훑어가며, 지금 가리키고 있는 숫자가 이전의 숫자보다 크다면 지금 숫자를 이전 숫자 대신 사용하는 것이 보다 큰 수를 만들 수 있는 방법이다.

풀이

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

스택을 사용하면 편하다.
자릿수를 유지해야 하고, 자릿수가 결과에 큰 작용을 하기 때문에 후입선출식 스택이 적합하다.
지금의 수와 이전의 수를 비교해 지금의 수가 크고 기회가 남아있다면 이전의 수를 배열에서 제거한다.
기회가 사라질때 까지 반복하며 탐색이 끝났다면 스택 그대로 문자열로 바꿔 반환한다.