백준 2812번 크게 만들기 (Python)

문제

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

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

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

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

정답 코드

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]):
    ## 만약 스택의 숫자가 지금 숫자보다 작다면
    ## 스택 안에 있는 숫자들을 모두 지워주고
    ## k를 그만큼 감소시킨다. 
    stack.pop()
    k -= 1
  stack.append(num[i])

print(''.join(stack[:n - _k]))

문제 해결 접근

• 처음에는 스택으로 풀 생각을 안 하고, n-k 길이의 정답 리스트를 설정해놓고, 현재 칸에 들어갈 수 있는 숫자들의 범위를 지정한 다음에, 그 중 가장 큰 숫자를 선택해서 넣어주는 방식을 생각했다.

import sys

input = sys.stdin.readline

n, k = map(int, input().strip().split())
numbers = list(map(int, list(input().strip())))

final_number = [0] * (n - k)
next_start = 0

for idx in range(n - k):
  ## 현재 칸에 들어갈 수 있는 숫자들
  # print("***")
  current = numbers[next_start:(k + idx + 1)]
  # print(current)

  ## 그 중 가장 큰 숫자를 넣어주기
  final_number[idx] = max(current)
  # print(final_number)

  ## 넣어준 숫자 이후로 current를 설정하기
  next_start = current.index(final_number[idx]) + next_start + 1
  # print(next_start)

print(''.join([str(i) for i in final_number]))

• 그러나 이 방식으로 풀면 정답은 나오지만 시간 초과가 뜬다. 다시 보니 입력이 50만개까지 있을 수 있으므로 시간 초과가 날 수 있을 거 같았다. (current에서 max를 찾아오는 함수를 호출하고, index를 다시 뽑아주는 과정에서 서치가 들어가서 시간 초과가 나는 것 같다.)
• 결국 답답해서 검색으로 정답을 찾았다. 해결의 key는 맨 앞 숫자부터 스택에 넣어주면서, 작은 숫자들은 k번 지워준다는 컨셉이다.
• 결국엔 그리디적으로 순서는 유지하되, 제일 큰 숫자가 스택 안에 있게 되고, 작은 숫자들은 k개 지워져서 정답이 나온다는 컨셉이다.
• 아직 많이 익숙하지는 않아서 해당 문제 유형들을 더 접해봐야 할 것 같다.