1. Problem 📃

📚 출처 - 프로그래머스

문제 설명
어떤 숫자에서 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"

2. Logic 👨‍🏫

2.1 조합과 정렬: 실패😂

시간 초과가 났던 풀이 방식입니다. 실제로도 제한 조건이 100만 자리 이하의 자연수이기 때문에 시간 초과 날것을 예상했지만 단순한 풀이 방법이라 풀어보았습니다.

2.1.1 알고리즘

순서에 상관 없이 모든 경우의 수를 만들고, 그 후 정렬해 가장 큰 값을 반환해주는 풀이입니다.

2.2 Stack(LIFO): 성공😋

이번 풀이는 살짝 구글링의 도움을 얻어 풀어보았습니다. stack을 활용해서 문제를 풀 수 있다는 것을 알게돼 push와 pop 두 가지를 사용해서 풀이하는 방식을 생각해 보았습니다.

• 핵심은 스택의 마지막 값이 push 할 값보다 작다면 크거나 같은 값이 나올 때까지 값들에 대해 pop을 하는 것입니다.
• 이렇게 풀이하면 O(n)의 시간 복잡도로 문제를 해결할 수 있습니다.

2.2.1 알고리즘

1. 스택 생성
2. number를 순회 => for i in number
   1. 다음 조건문을 모두 만족할 경우 반복
   2. 조건문
      1. k > 0
      2. 스택이 비어있지 않음
      3. 스택 마지막 값 < num
         2. 명령문
            1. 스택을 pop
               2. k--
   3. 스택에 i값을 push
3. k > 0 이상이면 스택에서 k개 삭제 후 join해서 결과 값 반환

3. Code 💻

1. 조합과 정렬😁

from itertools import combinations # 조합

def solution(number, k):
    answer = list(map(''.join, combinations(list(number), len(number)-k)))
    return sorted(answer, reverse=True)[0]

2. Stack(LIFO) 활용😁

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