소스코드
import sys
input = sys.stdin.readline
N,K = map(int, input().strip().split())
nums = list(map(int, input().strip()))
stack = []
removed_cnt = 0 # 제거한 원소 개수
for i in range(N):
while stack and stack[-1] < nums[i] and removed_cnt < K:
stack.pop()
removed_cnt += 1
stack.append(nums[i])
# 남은 개수만큼 뒤에서 제거
if removed_cnt != K:
stack = stack[:-(K-removed_cnt)]
print(''.join(map(str, stack))
Python
복사
풀이
•
앞자리부터 작은 수들을 최대한 제거해내는게 중요하다는 것을 여러 예시를 작성해보며 캐치했습니다.
•
그 과정에서 자료구조는 스택을 사용했습니다. 이유는 가장 마지막에 쌓은 값이 버릴 값이면 버리기 위해서 입니다.
•
선형탐색하면서 만약 넣을 값이 스택의 최상단 값보다 큰데 아직 K만큼 버리지 않았다면 스택에서 pop해줍니다.
◦
그리고 스택에 append해줍니다.
•
저도 마지막 부분을 캐치를 못했는데요, 모든 원소를 스택에 추가했더라도 아직 K만큼 버리지 않았을 수도 있습니다. 항상 스택의 최상단값이 들어올 값보다 클 수 있으니까요:D
◦
그러한 경우가 있을 수 있기에, 아직 K만큼 버린게 아니라면 뒤에서 (K-removed_cnt)만큼 슬라이싱해줍니다.
•
스택의 원소를 이어붙여 출력하면 끝!!
복기
•
while문을 잘 사용하지 않으려는 듯 하다. 본능적으로 기피하는 것 같은데 왜 그런지 모르겠다. 계속 사용하도록 노력해봐야지
•
마지막에 removed_cnt가 K가 안되었을 수 있음을 캐치하지 못했다. 마지막까지 좀 더 꼼꼼히 경우를 처리해줘야지
•
다음 번에 풀 때는 좀 더 시간을 타이트하게 잡아놓고 풀어보자. 골드 문제를 좀 더 스테디하게 풀어낼 수 있어야할 듯 하다.