[python] 백준 2812 :: 크게 만들기 (스택)

[크게 만들기]

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

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

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

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

풀이

• 뒤에서 아무리 큰 숫자가 나와봤자, 앞에 있는 숫자들의 개수가 지울수 있는 총 개수보다 많으면 소용이 없다.
• 앞에서부터 하나씩 비교해가면서 지울 수 있는 개수만큼 지워나가야 한다.

👇🏻 요로케

• 숫자를 앞에서부터 하나씩 떼어서 그 앞에 나왔던 숫자보다 큰 숫자인지 확인한다.

• 지금 숫자가 앞에 나온 숫자들보다 큰 숫자이고, 제거할 수 있는 숫자의 개수가 남아있으면 그 숫자를 지워버린다!

전체 코드

n, k = map(int, input().split())  
number = input()  

stack = []  # 남길 수열을 저장할 스택
remove_count = k  # 제거해야 할 숫자의 개수

for num in number:  # 수열의 각 숫자를 하나씩 순회
    while stack and remove_count and stack[-1] < num:
        # 스택이 비어있지 않고, 
        # 아직 제거해야 할 숫자가 남았으며, 
        # 스택의 마지막 숫자가 현재 숫자보다 작을 경우

        stack.pop()  # 지금 비교한 숫자 제거
        remove_count -= 1  # 제거해야 할 숫자의 개수를 1 감소시킴

    stack.append(num)  # 현재 숫자를 스택에 추가

# 선택한 수열에서 k개의 숫자를 제거하여 만들 수 있는 가장 큰 수를 출력
print(''.join(stack[:n-k]))

🚨출력 주의사항

• 아래 예시처럼 맨 마지막의 숫자가 지워져야 하는 경우가 있을 수 있다.

# 입력
5 1
54321

# 답
5432

• 출력할 때 숫자의 총길이에서 지워야 할 개수를 뺀 만큼만 출력하도록 해야 한다.
  (이렇게 안하면 72%에서 틀렸습니다가 나온다ㅎㅎ😠)