[복기] 2812번: 크게 만들기

문제

백준 2812번: 크게 만들기

알고리즘 분류

• 자료구조
• 스택
• 그리디 알고리즘

나의 풀이

숫자를 문자열로 받아서, 왼쪽에서 오른쪽으로 가면서 수를 담고, 스택 top보다 크면 다 빼버린다. 남은 자리수와 빼야할 개수 K를 비교하면서 더 뺄지말지를 결정한다.

끝이다. 로직은 무척 간단한데, 나는 쓸데없이 if문을 많이 달아서 더럽게 복잡해졌다.. 아래의 솔루션을 보면 알겠지만 정말 간단하게 처리할 수 있는데.. 자잘한 예외처리를 if문으로 각개 처리해줘서 복잡해졌다.

코드

n, k = map(int, input().split())
number = input()

stack = []
for i in range(n):
    if not stack:
        stack.append(number[i])
    else:
        top = int(stack[-1])
        cur = int(number[i])
        if k > 0:
            if n-i >= k:
                if top < cur:
                    while stack and k > 0:
                        if int(stack[-1]) >= cur:
                            break
                        stack.pop()
                        k -= 1
                    stack.append(number[i])
                else:
                    if n-i == k:
                        k -= 1
                    else:
                        stack.append(number[i])
                        
        else:
            stack.append(number[i])

for s in stack:
    print(s, end='')

솔루션

크게 만들기 풀이

풀이 로직은 앞서 설명한 것과 동일하다.

코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
numbers = input().rstrip()

stack = []
for number in numbers:
    while stack and stack[-1] < number and k > 0:
        stack.pop()
        k -= 1
    stack.append(number)
    
if k > 0:
    print(''.join(stack[:-k]))
else:
    print(''.join(stack))