[Python] 백준 #2812 크게 만들기(탐욕 알고리즘)

이번 문제는 n개의 자리를 가진 숫자에서 k개의 자리수를 제거하여 n-k개의 자리를 가진 수 중에 가장 큰 수를 만드는 것입니다.

 

making biggest number

 

문제의 링크는 다음과 같습니다.

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

 

저는 스택(stack)을 이용한 탐욕 알고리즘을 이용해서 문제를 풀었습니다.  알고리즘은 간단합니다.  다음수가 맨 마지막수보다 크고 빼어야할 수가 있다면, 맨 마지막수를 빼고 다음수를 추가하는 방식입니다.

 

입력 받기

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

- 이 부분은 `n`과 `k`를 입력받습니다. `n`은 문자열 `s`의 길이, `k`는 제거할 문자 개수를 의미합니다.

스택 초기화

stack = ["9"]

- 가장 큰 수를 만들기 위해 사용할 스택을 초기화합니다. 스택의 첫 번째 원소로 "9"를 넣는 이유는, 비교를 위해 무조건 큰 값을 넣어놓는 것입니다. 이렇게 하면 스택이 비어 있는 상태와 동일하게 취급할 수 있습니다.

입력된 문자열 받기

s = input()

- 문자열 `s`를 입력받습니다.

변수 초기화

t = k

- 남은 제거 횟수를 `t`에 저장합니다. 나중에 이 값을 활용하여 문자를 제거할 수 있습니다.

문자열 순회

for c in s:
    while t > 0 and stack[-1] < c:
        stack.pop()
        t -= 1
    stack.append(c)

- 문자열 `s`의 각 문자 `c`를 순회합니다.
- 스택의 마지막 문자(`stack[-1]`)가 현재 문자 `c`보다 작고, 제거할 수 있는 횟수(`t`)가 남아 있다면, 스택에서 문자를 제거합니다.
- 그런 다음, 현재 문자 `c`를 스택에 추가합니다.

결과 출력

print("".join(stack[1:n-k+1]))

- 스택의 첫 번째 원소는 제거하고, 스택에서 길이가 `n-k`인 가장 큰 수를 반환합니다.

파이썬으로 만들어진 전체 소스입니다.

n, k = map(int, input().split())
stack = [ "9" ]
s = input()
t = k
for c in s:
    while t > 0 and stack[-1] < c:
        stack.pop()
        t -= 1
    stack.append(c)
print("".join(stack[1:n-k+1]))