크게 만들기 - 2812번

문제

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

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

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

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

풀이

오답

다음의 코드는 오답이다. 처절하게 틀렸다.

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
number = list(map(int, input().strip()))

stack = []

for i in range(N):
    while K>0 and stack and stack[-1]<number[i]:
        stack.pop()
        K-=1
    stack.append(number[i])

# 오답
result = ''
for n in stack:
    result += str(n)
print(result)

일단... stack을 이용한 풀이이다.

왜 처절하게 틀렸냐면, 위 for문 while문 구간이 절묘했다 한들 문제를 절반밖에 안 푼 격이기 때문이다.

풀이하면 이렇다.

for문의 i==0회차 때, 가장 먼저 임시보관용 변수 stack에 입력된 숫자가 리스트화 된 리스트 변수 number의 가장 첫번째 요소가 담긴다. 그러면서 i==1회차로 곧장 넘어가며 바로 직전 회차의 for문 수행에서 stack에 담긴 stack[-1], 말인즉 number[i-1]와 number[i]의 크기를 비교한다.

이렇게 while문 안의 조건문 안팍을 돌면서 각 자리 숫자들은 순서대로 크기가 비교당하고, 큰 숫자들만 stack에 남고 작은 숫자들은 pop되며, 그렇게 K-1번 while문을 도는 것으로 for문의 i회차 순회가 종료되는 것. 이후 또 for문의 i+1회차를 돈다.

그런데 이 while문 안 for문은 하는 수 없이 그 비교에 방향성이 정해져 있어서(i의 오름차순), 의도와 다른 오류가 발생한다.

stack에 먼저 담긴 i-1째자리 숫자(number[i-1], == stack[-1])가 현재의 i째자리 숫자(number[i])보다 크면, stack에 무조건 담긴다. 말인즉 현재의 i째자리 숫자가 작을 때만 기존의 stack에서 pop이 일어나고 그 반대의 경우는 stack에서 pop이 안 일어나는 채 그냥 stack에 숫자가 담기기만 한다.

위와 같은 이유로 543210, 32111 등의 반례들이 속출한다.
즉, 앞의 숫자들이 뒤의 숫자들보다 큰 숫자의 경우에는 while문 안을 안 돌거나 덜 돌고 그냥 나온다는 것.

그래서 한 번 더 공정이 필요한 거다.
while문을 K-1번 돌지 않은 경우, 즉 for문을 다 돌았는데도 여전히 K!=0인 경우를 방어해야 함이다.

정답

아래의 코드는 정답이다.

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
number = list(map(int, input().strip()))

stack = []

for i in range(N):
    while K>0 and stack and stack[-1]<number[i]:
        stack.pop()
        K-=1
    stack.append(number[i])

result = ''
for n in stack[:len(stack)-K]:
    result += str(n)

print(result) 

짠~
역시 마지막 프린트 직전 구간을 봐야 한다.

result = ''
for n in stack[:len(stack)-K]:
    result += str(n)

stack[:len(stack)-K]: 는 리스트 변수 stack의 뒤에서부터 K번째인 거 전까지 슬라이스한다는 구문.

이때 기억할 점은, K는 for문을 돌면서 0이 되었다는 점이다.
그런데 이는 우리가 처음 기대했던 while문 안을 다 잘 돌고 나오는 경우에만 해당하고, 아까 말한 경우들은 K가 여전히 자연수이다.

그렇다면 stack[:len(stack)-K]:는 무슨 뜻이냐면....
우리가 처음 기대했던 while문 안을 다 잘 돌고 나오는 경우에는 K==0이므로 슬라이스 구문에서도 짤릴 게 없는 그대로의 stack이고,
K!=0인 경우에는 딱 그만큼의 자릿수가 짤린다는 것이다.