[알고 스터디] 1. 스택(Stack) - 2812

백준 2812번 - 크게 만들기 - 골3

문제

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)

둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

출력

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

예제 입력 1

4 2
1924

예제 출력 1

94

예제 입력 2

7 3
1231234

예제 출력 2

3234

예제 입력 3

10 4
4177252841

예제 출력 3

775841

---

[풀이]

문제도 간결하고 뭔가 깔쌈하고 흥미로워 보여서 내가 추천한 문제이당!

근데 스터디원들이 10분동안 생각하면서 접근방식 나눠보니까 굉장히 빠르게 정답을 생각해주셔서 좀 더 재밌고 흥미있었던것같다 ㅋㅋ

 

이 문제는 확실히 스택을 이용해야 빠르다, 왜냐? 리스트 빼고 리무브 하고 있는거보다, 스택에서 pop 하는게 빠르니까.

그리고 이건 또 좀 사고력을 요하는 문제인데, 

숫자에서 큰 자리 수의 숫자가 커야 수가 커진다는 걸 잘 인지하면 될 것 같다.

가령 1999999 이런게 아니라 91111111 이런게 더 큰거처럼? 앞의 수가 커질수록 이득!

--> 이 말은 즉슨, 내가 자릿수로 스택을 쌓을때, 이전 저장된 숫자보다 다음 담을 숫자가 크다면 빼면 좋다는거지!

 

예를 들어서

그림으로 보자면 약간 이런거지 히ㅣ히ㅣ,,,, 하하 발그림 ㅈㅅ

 

하여튼 !! 아주 좋은 접근 방식이라 한수 배워갑니다 ㅎㅎㅎㅎㅎ 재밌따

 

## import lib
import sys

## main
num, delete_num = map(int, sys.stdin.readline().split())
input_num = sys.stdin.readline().split()[0]
number_stack = []

# 나중에 delete_num이 다 안빠질 수도 있어서 체크용
left = len(input_num) -1
for i in range(len(input_num)):
    if delete_num == 0:
    	# 다 빠졌다면 끝내고 남은 숫자 수 left에 저장
        left = i
        break
    # delete_num > 0 이라면 앞에 수가 나보다 클때까지, 계속 제거할 수 있음
    while(len(number_stack)):
        if delete_num == 0:
            break
        if number_stack[-1] < int(input_num[i]):
            number_stack.pop()
            delete_num -= 1
        else:
            break
    number_stack.append(int(input_num[i]))

# 만약 delete_num이 남아있다면 스택에서 초과한만큼 제거,,
if left >= len(input_num)-1:
    if delete_num > 0:
        while (delete_num):
            number_stack.pop()
            delete_num -= 1
    total = 0
    i = 1
else:
    total = int(input_num[left:])
    i = 10**(len(input_num[left:]))

# 10단위로 늘려가면서 pop 하면서 더하기~
while(len(number_stack) != 0):
    total += i * (number_stack.pop())
    i *= 10
print(total)