[백준] 2812 크게 만들기

✔️ 문제 링크

https://www.acmicpc.net/problem/2812

💡 핵심 아이디어

1️⃣ 스택구조와 탐욕기법을 사용

2️⃣ 왼쪽자리에 있는 수 부터 스택에 넣어주며 새로 넣어주는 수보다 큰 수가 스택 top 부분에 있을 때 까지 스택에서 수를 비워준다.(이때, 예외처리로 K개를 제외하였을 경우 제거 작업을 그만하고 나머지 조사하지 않은 수 들을 스택윗부분에다가 추가, 만약 스택이 비었을 시에는 넣어주려는 수를 스택에 넣어줌) -> 되도록이면 큰 수를 자리수가 큰 부분에 위치하기 위한 탐욕적 방법을 사용

⭐️ 소스 코드

if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    num = input()

    s = [num[0]]
    remove_count = 0

    for i in range(1, len(num)):

        if remove_count == K:
            s += num[i:]
            break

        while True:

            if len(s) == 0:
                s.append(num[i])
                break
            elif num[i] > s[-1]:
                s.pop()
                remove_count += 1
            else:
                s.append(num[i])
                break

            if remove_count == K:
                s.append(num[i])
                break

    ans = ''.join(s[:N - K])
    print(ans)