성능 요약
메모리: 157092 KB, 시간: 184 ms
분류
자료 구조, 그리디 알고리즘, 스택
문제 설명
N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)
둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.
출력
입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.
아이디어, 문제풀이
- 가장 중요한건, 자리수 생각할 필요 없이 지운다는것이다.
- 어짜피 같은 개수의 숫자를 지우기 때문에, 지운 이후에 크기를 비교할때, 단순 크기비교만으로 문제풀이가 가능하다.
- 그렇기에, 스택을 활용하는 방법이 맞다.
TROUBLE SHOOTING
-
일단, 나는 스택이 아닌 수식을 구현해 최대한 구현해보려고 노력했는데, 시간초과가 나왔었다. 결국, 스택을 또 활용해야했고, 마땅히 떠오르는 알고리즘이 없어 구글링을 했었는데, 소름돋게도 모든 코드들이 동일했다.. 이미 이 문제는 이풀이가 확정이고 외워야 되는것처럼… 까진 아니겠지만, 코드를 이해하는데에 꽤 많은 시간을 썼던것 같다.
이해한대로 설명해보자면, 결국 완전탐색과 비슷한 알고리즘이고, 그 과정속에서 우리가 설계한 반복문을 통해 올바른 값을 집어넣도록 하면되는 문제였다. while문의 조건들이 좀 나 혼자 생각할수 있을까? 정도로 잔인했다 생각했는데, 이해하고 나니 그래도 나에게 시간이 많았다면 풀만 했던것 같다. -
여기서, k라는 값이 어떻게 변하는지를 지켜봐야하는데, 나는 입력받은 k값을 k -= 1 를 통해서 while문을 작성했기 때문에, 출력때 k만큼덜 출력하고 싶다는 코드를 작성할때에 지속해서 오류가 났다. 배열의 길이보다 더 많은값을 출력하려 했기 때문이다. (당연하다ㅠ)
임의로 k_first 변수를 만들어 입력받은 k값을 따로 저장했고, 그 값을 통해 출력했다. 아래는 이 문제를 해결하기 위한 chat gpt와의 소통중 일부다.- 문제에서 주어진 조건에 따르면, 주어진 숫자를 이루는 숫자 중 K개를 지워서 얻을 수 있는 가장 큰 수를 출력해야 합니다. 처음에는 K개의 숫자를 지워야 하기 때문에
k_first = k를 선언하여 처음의 K값을 저장합니다. stack[:n-k_first]를 사용하는 이유는 최종적으로 출력할 숫자의 길이가 N-K가 되어야 하기 때문입니다. 알고리즘을 수행하면서 K값이 줄어들지만, 출력할 때는 처음의 K값을 사용하여 슬라이싱을 해야 올바른 결과를 얻을 수 있습니다.- 예를 들어, N=10, K=4인 경우 주어진 숫자에서 4개의 숫자를 지워 6개의 숫자로 이루어진 가장 큰 수를 출력해야 합니다. 알고리즘이 수행되면서 K값은 줄어들겠지만, 최종 출력할 때는 처음의 K값을 사용하여 슬라이싱을 해야 올바른 결과를 얻을 수 있습니다. 따라서
stack[:n-k_first]를 사용하여 최종적으로 출력할 숫자의 길이를 N-K로 맞춥니다.
- 문제에서 주어진 조건에 따르면, 주어진 숫자를 이루는 숫자 중 K개를 지워서 얻을 수 있는 가장 큰 수를 출력해야 합니다. 처음에는 K개의 숫자를 지워야 하기 때문에
코드
#https://www.acmicpc.net/problem/2812
#크게 만들기
#2812
from collections import deque
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
n_list = list(input().strip())
#이문제에서 제일 많이 해맨부분
k_first = k
# print(n_list)
stack = []
# stack = deque()
# deque객체에서는 슬라이싱을 지원하지 않고있다.
for i in range(n):
while k > 0 and stack and stack[-1] < n_list[i]:
stack.pop()
k -= 1
stack.append(n_list[i])
print(''.join(stack[:n-k_first]))