1. 문제
N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)
둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.
출력
입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.
2. 정답 코드
n, k = map(int, input().split())
check = k
ls = list(input())
stack = []
for i in ls:
while len(stack) > 0 and stack[-1] < i and k > 0:
stack.pop()
k -= 1
stack.append(i)
print("".join(stack[:n - check]))3. 생각한 방향 및 설명
처음에는 무지성으로 heapq를 써서 가장 작은거 다 골라내면 큰 값만 남으니까 그거 출력하면 되겠지? 라는 생각을 했었다. 하지만 하나 놓치고 있었던 것이 있었다.
여기서는 골라서 숫자를 만드는 문제가 아니라 순서가 정해진 그 상태에서 하나씩 숫자를 빼면서 새로운 숫자를 만들어야 했다. 그래서 heapq방법은 포기…
그 다음 생각했던 것은 큰 수를 가장 높은 자리수로 만들어주어야 하고, 순서가 정해져 있기 때문에 → 차례대로 스택에 넣으면서 만약 기존에 들어있던 값들이 새로 들어오는 값보다 작으면 전부 pop해버리는 방법을 생각해 냈다.
Q.만약 기존 숫자와 새로 들어오는 숫자의 크기가 같으면?
일단 넣어둬. → 같을 때 빼도 값이 변하지 않기 때문. ex) 67에서 7이 들어오면 기존에 7을 빼고 새로운 7을 넣으면 다시 67이 됨.
코드1
n, k = map(int, input().split())
ls = list(input())
stack = []
for i in ls:
while len(stack) > 0 and stack[-1] < i and k > 0:
stack.pop()
k -= 1
stack.append(i)
print("".join(stack))하지만 여기서 문제가 생겨버렸다.
예시 입력
n = 4, k = 2
숫자 : 1111
이렇게 들어오면 다 같기 때문에 k가 빠지지 않아서 최종 결과값이 1111이 되어버린다.
그래서 이 사태를 막기 위해 아래와 같이 처리했다.
코드2
n, k = map(int, input().split())
ls = list(input())
stack = []
for i in ls:
while len(stack) > 0 and stack[-1] < i and k > 0:
stack.pop()
k -= 1
stack.append(i)
print("".join(stack[:n - k]))
# 같은 값이 들어오면 k값이 빠지지 않아 생기는 문제 해결?여기서 또 문제가 발생했다. 바보같은 실수를 했다.
내가 생각한 것은 최종 결과값 자릿수만 맞춰주면 되겠다고 생각해서 단순히 n-k라고 했지만 잘 살펴보면 k값은 변하고 있는 숫자이다. 원하는 자릿수 설정이 제대로 안되는 버그가 생기는 것이다.
최종코드
n, k = map(int, input().split())
check = k # 버그 수정
ls = list(input())
stack = []
for i in ls:
while len(stack) > 0 and stack[-1] < i and k > 0:
stack.pop()
k -= 1
stack.append(i)
print("".join(stack[:n - check]))