[백준] #2812 크게 만들기 (python)
2812번: 크게 만들기
N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
문제
N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)
둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.
출력
입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.
예제 입력 1 복사
4 2
1924예제 출력 1 복사
94예제 입력 2 복사
7 3
1231234예제 출력 2 복사
3234예제 입력 3 복사
10 4
4177252841예제 출력 3 복사
775841
# Code
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
stack = []
number = list(input().rstrip()) # rstrip() 안 해주면 뒤에 \n 원소도 생김
for i in range(n):
while k>0 and stack and stack[-1] < number[i]:
stack.pop()
k-=1
stack.append(number[i])
print(''.join(stack[:len(stack)-k])) # 다 돌고 나왔는데 k 가 0 이상일 경우# Comment
무조건 앞에서부터 작은 수들을 빼가면서 풀면 되겠다... 라고 막연히 대충 생각하고 풀이 딱 짰는데 마지막 3번 테스트 케이스 같은 경우 때문에 안 된다는 것을 나중에 깨달아버린...
고민 하다가 음.. 이렇게 풀면 안 될 것 같은데 생각이 안나서 다른 풀이를 참고했다. 보니까 스택을 이용해서 풀면 되는 문제였다 ..^^ 오랜만이군
앞에서부터 스택에 주어진 숫자를 하나씩 집어 넣으면서 스택에 가장 최근에 들어온 값과 새로 들어온 값을 비교해서 스택에 들어있는 값이 더 작으면 pop 해주는 것이 알고리즘이다.
값을 하나씩 pop해줄 때마다 k 값을 하나씩 줄여주는 것.. 잊으면 안 된다. 만약에 pop할 것이 없다면 새로운 값을 number 리스트에서 받아온다.
** 마지막에 출력할 때 간과했던 부분이 있는데 for문을 다 돌고 나왔음에도 k 값이 0 이상일 경우가 발생할 수 있다.
이럴 경우엔 앞에서부터 len(stack)-k 까지 출력해줘야 하는데, 여기서 처음에 n-k로 계속 작성해서 틀렸었다. 나는 k를 대체할 다른 변수를 두지 않고
k 값 그 자체에서 --를 했기 때문에 마지막에 뺄 때 온전한 k의 값이 아닌 남아있는 k 값을 빼는 것이기 때문에! 남아 있는 스택의 길이 중에서 k를 빼줘야 하는 것이었다..!!