[백준] 2812번 크게 만들기, 파이썬 문제 풀이

문제

백준 2812번 주어진 숫자에서 K개의 숫자를 없앴을 때 가장 큰 수를 만드는 문제를 해결했습니다.

문제

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

입력

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

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

예시: 7 3

        1231234

출력

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

예시: 3234

 

풀이 과정

그리디 알고리즘으로 해결할 수 있는 문제를 찾았기 때문에, 그리디 알고리즘으로 접근했습니다. 그리디 알고리즘이란, 현재 선택할 수 있는 가장 최적의 선택을 하는 것입니다. 당장은 최적의 선택일 수 있어도, 전체적으로 봤을 때 최적을 보장하지 않는 알고리즘입니다. 

 

스택을 사용해서, 첫 번째 숫자부터 시작해서 가장 큰 숫자를 스택에 넣고, 작은 숫자가 있으면 제거합니다. 이 과정을 K번 만큼 진행하면, K개의 숫자가 사라지기 때문에 가장 큰 숫자를 만들 수 있습니다.

 

이러한 논리가 가능한 이유는 결국, 숫자의 순서는 바뀌지 않기 때문입니다. 앞에서부터 숫자를 골라 K개를 걸러내고 만들어 낸 숫자보다, 뒤에 더 큰 숫자를 앞으로 빼서 더 큰 숫자를 만들어 낼 수 있습니다. 주어진 예시로 예를 들면, 결과는 3234입니다. 하지만, 우리는 4332가 더 큰 숫자임을 알고 있습니다. 그럼에도 불구하고, 숫자의 순서는 바꾸지 않고 큰 숫자를 만들어야 하기 때문에 4가 맨 뒤로 빠지는 것입니다.

이것이 그리디 알고리즘에서 전체적으로 봤을 때 최적을 보장하지 않는다는 것입니다. (물론, 이 문제는 숫자의 순서를 변경하지 않으므로, 전체적으로 봤을 때도 최적인 것은 맞다고 생각합니다.)

 

이를 코드로 표현하면 다음과 같습니다.

N, K = map(int, input().split())
num = list(input())
k = K
stack = []

for i in range(N):
    while(k > 0 and stack and stack[-1] < num[i]):
        stack.pop()
        k-=1
    stack.append(num[i])
    
print(''.join(stack[:N-K]))

스택이기 때문에 [-1]인덱스를 넣어 뒤부터 검사하는 것을 볼 수 있습니다. 

결과값 출력에 사용된 join() 함수는 리스트안에 있는 문자를 문자열로 바꾸어주는 함수입니다.

 

정리

그리디 알고리즘과 스택 자료구조를 활용해서 문제를 해결했습니다. 다른 분들의 풀이를 찾아보니, 비슷한 내용으로 해결하신 분들이 많은 것 같습니다. 스택을 활용하지 않으면 시간 초과가 발생합니다.