백준 2812 크게 만들기

처음 생각

• 스택에 인덱스를 저장하기
• 리스트 전체를 순회하며 스택 마지막 값이 크면 그냥 추가, 스택 마지막 값이 작으면 큰 값이 나올 때까지 뺀 후, 추가.

시행착오

1. 맨 앞자리부터 하나씩 수를 구하기

• 리스트 구간을 바꿔가며 해당 구간에서 스택을 만들고, 가능한 수를 앞부터 하나씩 구해간다.
  • 시간 초과 - 중복하는 계산량이 너무 많아진다.

2. 엣지케이스

• 마지막에 값을 추가하고 연산이 끝날 것으로 생각했다.
• 그러나 무조건 마지막에 값을 추가하게 되면 그 전에서 조건을 만족한 경우, 필요 없는 값을 추가하게 된다.
• 반례

  5 3
  94111

코드 설명

1. 스택에 값을 저장하고, 빼는 과정을 반복한다.
2. 스택의 총 길이와 남은 리스트 항목 수를 비교해서, 남은 항목을 모두 추가해야하는 상황이면 빼지 않고 추가만 한다.
3. 스택의 길이가 조건을 만족하지 않을 때만 항목을 추가한다.

N, K = map(int, input().split())
lst = list(map(int, input()))

stack = []

for i in range(N):

    if len(stack) == 0:
        stack.append(i)
        continue

    while lst[stack[-1]] < lst[i]:
        if i == K+len(stack):
            break
        stack.pop()
        if len(stack) == 0:
            break

    if len(stack) < N-K:
        stack.append(i)

for k in stack:
    print(lst[k], end="")