문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

입출력 예

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

접근 방법

처음에는 i번째 수가 i+1번째 수보다 작을 경우 i번째 수를 지우는 방식으로 작성하였다. 그러나 테스트 케이스에서 실패하였고 여러가지 방법들을 고민하던 중에 스택을 사용하라는 힌트를 찾았다.

스택에 number의 i번째 수를 넣고 스택의 -1번째 수가 number의 i번째 수보다 크거나 같아질때까지 스택을 pop한다. 이 과정을 number전체를 순회하며 반복한 뒤에 스택에 있는 수들을 문자열로 합쳐 해결하였다. 여기서 만약 지운 수의 개수가 k보다 작을 경우에는 스택의 [:-k]만을 취한다.

• 스택으로 사용할 배열 answer를 선언한다.
• number를 순회하는 i에 대한 for문을 돌린다.
  -> 만약 answer가 비어있다면 answer에 i를 넣고 다음 반복으로 넘긴다.
  -> 만약 k가 0보다 클 경우,
  --> answer[-1]이 i보다 작을 동안 반복하는 while문을 돌린다.
  ---> answer를 pop하고, k를 1 감소시킨다.
  ---> 만약 answer가 비어있거나 k가 0보다 작거나 같다면 while문을 탈출한다.
  -> answer에 i를 넣는다.
• 만약 k가 0보다 클 경우, (지운 수가 k보다 적을 경우)
  -> answer를 answer[:-k]로 갱신한다.
• 결과를 넣을 변수 result를 선언하고 answer를 문자열로 넣는다.
• result를 반환한다.

solution.py

def solution(number, k):
    answer = []
    for i in number:
        if not answer:
            answer.append(i)
            continue
        if k>0:
            while answer[-1]<i:
                answer.pop()
                k-=1
                if not answer or k<=0:
                    break
        answer.append(i)
    if k>0:
        answer=answer[:-k]
    result=''.join(answer)
    return result