[BOJ][Python] 백준 2812번: 크게 만들기

1일 1PS 38일차!

📚 문제

---

골드 3

• 주어진 수의 처음부터 훑어나가며 이전보다 큰 수가 들어왔다면 이전의 작은 수들을 지워나가면 된다.

💡 풀이 과정

---

1. num 의 수를 하나하나 체크하면서 지울 횟수가 남아있는지, 이전의 수를 비교할 수 있는 지와 비교했을 때 지금의 수가 더 큰지 확인한다.
2. 위의 조건이 맞으면 이전의 수를 제거하고 지울 횟수를 차감한다.
3. 지울 횟수를 모두 사용했다면 모든 수를 append 한다.
4. 답은 N-K 자리수 이므로 result를 자릿수에 맞춰 출력한다.

📌포인트

---

• Stack
  • 처음에는 이전의 수들을 모두 비교했었고 당연히 시간초과가 발생했다.
  • 이후에 N 만큼의 크기로 Boolean indexing 을 해봤지만 역시 시간초과가 발생한다.
  • Stack 을 사용해야 시간초과가 발생하지 않는다.
• result[N-K]
  • N 자리 숫자에서 K 개의 숫자를 제거하기에 정답은 N-K 자리이다.
  • 54321 이라는 숫자가 주어지면 K 에 관계없이 result 에는 모든 숫자들이 들어가게 되고, 이를 N-K 자리까지만 출력해주어야한다.

💻 코드

---

N, K = map(int, input().split())
num = input()
k = K

result = []

for n in num:
    while k > 0 and result and result[-1] < int(n):
        result.pop()
        k -= 1
    result.append(int(n))

print("".join(map(str, result[:N-K])))