[파이썬 PYTHON] 백준 2812번 【크게 만들기】

---

문제 접근 방법을 예제로 설명해보겠다.

10 4
4177252841

위와 같이 10개의 숫자가 주어지고, 4개의 숫자를 삭제할 수 있다.

 

가장 큰 수를 출력하기 위해서는, 앞의 자리수가 커야한다.

 

앞 자리 수부터 하나씩 스택에 넣을 것인데, 

 

 

 

스택에 들어갈 수가 스택에 들어있는 수보다 큰 경우 & 삭제 횟수가 남아있는 경우 

 

스택에 있는 숫자를 지울 것이다.

 

예시로 보면

 

---

현재 answer 스택 = [] 은 비어있다.

 

4177252841 수를 앞 자리 수부터 넣을 것이다.

---

answer 스택에 비교할 수가 없으므로 첫번째 자리는 일단 스택에 입력한다.

answer = [ 4 ] 

 

4 177252841 

---

이제 1을 넣을 차례인데, answer 스택 안에 있는 4가 더 크므로 일단 입력한다.

answer = [ 4 1 ]

 

41 77252841 

 

---

이제 7을 넣을 차례인데 answer 스택 안에 있는 1보다 크므로 1을 밀어낼 수 있다.

 

answer.pop()을 하면 answer = [ 4 ] 가 된다.

 

그리고 4와 비교했을 때도 7이 더 크다. 그러므로 answer.pop()을 한번 더 한다.

 

answer = [] 이 되고 비교할 수가 없으므로 7을 입력한다.

 

answer = [ 7 ] 이고 삭제 횟수 2번을 사용했다.

 

417 7252841

---

이제 7을 넣을 차례인데 answer 스택 안에 있는 7과 크기가 같으므로 밀어낼 순 없고 그냥 입력한다.

 

answer = [ 7 7 ]

 

4177 252841

 

---

이제 2를 넣을 차례인데, answer 스택 안에 있는 7보다 작으므로 밀어낼 수 없고 그냥 입력한다.

 

answer = [ 7 7 2 ]

 

41772 52841

 

---

이제 5를 넣을 차례인데, answer 스택 안에 있는 2보다 크므로 2를 밀어낼 수 있다.

 

answer.pop()을 하면 answer = [ 7 7 ] 이 된다.

 

근데, 5는 7보다는 작으므로 7을 밀어낼 순 없다. 따라서 그냥 입력한다.

 

answer = [ 7 7 5 ] 이고 삭제 횟수는 3번을 사용해서 1번 남았다.

 

417725 2841

---

2를 넣을 차례인데, answer 스택에서 밀어낼 수 있는 수가 없으므로 그냥 입력한다.

 

answer = [ 7 7 5 2 ]

 

4177252 841

 

---

이제 8을 넣을 차례인데, answer 스택의 2를 밀어낼 수 있다.

 

따라서 answer.pop()을 하면 answer = [ 7 7 5 ] 가 된다.

 

그리고 5보다도 크므로 5를 밀어낼 수 있지만, 삭제 횟수 4번을 모두 사용했으므로 그냥 입력한다.

 

answer = [ 7 7 5 8 ]

 

---

이제 남은 삭제 횟수가 없으므로 순차적으로 입력한다.

 

최종 answer = [ 7 7 5 8 4 1  ] 이 된다.

---

 

위 과정을  코드로 나타내면

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

numbers = list(input())
answer = []

for number in numbers:
    while (len(answer) > 0 and answer[-1] < number and K > 0):
        answer.pop()
        K -= 1
    answer.append(number)

while (K > 0):
    answer.pop()
    K -= 1

print(''.join(answer))

위와 같다.

 

그리고 N = 2 , K = 1 , 99 로 주어지는 케이스 같은 상황은 최종 결과가 9 이여야 하므로

 

그 부분을 고려한 while 문을 추가하면 된다.