[인프런] 가장 큰 수

---

문제설명

선생님은 현수에게 숫자 하나를 주고, 해당 숫자의 자릿수들 중 m개의 숫자를 제거하여 가장 큰 수를 만들라고 했다. 여러분이 현수를 도와주저야 한다. 단, 숫자의 순서는 유지해야 한다. 만약 5276823이 주어지고 3개의 자릿수를 제거한다면 7823이 가장 큰 숫자가 된다.

입력조건

• 첫째 줄에 숫자와 제거해야 할 자릿수의 개수가 주어진다.

출력조건

• 가장 큰 수를 출력한다.

사고과정

• 스택을 어떻게 활용해야 하나.. 매우 고민했다.. 스스로 능력으로 구현하는 데 도무지 아이디어가 나질 않아서 강의에서 문제 풀이 아이디어만 듣고 다시 도전해보았다. 결국 구현하긴 했지만 정답 풀이와 비교해보니 내 코드가 너무 만연하고 길어진 코드임을 알 수 있었다..
• 핵심 아이디어는 앞에서부터 스택에 숫자를 하나씩 넣으면서 탐색하는 숫자가 스텍의 마지막 원소값보다 크다면 스택안에 있는 모든 작은 값들을 모두 pop한다. pop할 때, 제거할 숫자 횟수에서 1을 차감한다. 단, 스택이 비거나 제거할 숫자 횟수가 0이 되거나 pop하다가 스택의 마지막 값이 탐색하는 숫자보다 커지는 값이 나왔다면 중단하고 탐색한 숫자를 스택에 append해준다.
• 입력예시가 2개로 주어졌는데, 첫 번째 예시는 숫자를 모두 탐색한 결과, 제거할 숫자 횟수(m)이 0보다 큰 즉, 아직 제거할 숫자 개수가 남지 않았을 경우이고 두 번째 예시는 제거할 숫자 개수가 0으로 모두 사용했을 때이다. 이 m이 0이냐에 따라 숫자를 출력해줄 조건을 달리하는 것도 주목해야 한다.

풀이(스스로 못 푼 풀이)

- 나의 풀이

n, m = input().split()
arr = list(map(int, n))
m = int(m)
stack = [arr[0]]

for i in range(1, len(arr)):
    if arr[i] <= stack[-1]:
        stack.append(arr[i])
    else:
        while len(stack) != 0 and arr[i] > stack[-1]:
            if m == 0:
                break
            stack.pop()
            m -= 1
        stack.append(arr[i])
stack = list(map(str, stack))
# print('m:', m)
# print('stack:', stack)
# print()
if m == 0:
    print(''.join(stack))
else:
    print(''.join(stack[:-m]))

- 강의 풀이(권장)

num, m = map(int, input().split())
num = list(map(int, str(num))) # 이렇게 할 수도 있구나!
stack = []

for x in num:
    while stack and m > 0 and stack[-1] < x:
        stack.pop()
        m -= 1
    stack.append(x)
if m != 0:
    stack = stack[:-m]
res = ''.join(map(str, stack))  # string을 map 활용해 join시키는 방법!
print(res)