[백준-파이썬] 2812: 크게 만들기

문제 보러 가기!

아이디어 ❄

N자리 숫자가 주어졌을 때, 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 만드는 문제였다!
처음에 한 생각은, '아! 그러면 쭉 보면서 작은 숫자 K개를 없애주면 되려나?' 였다.
1924에서 2개를 지우라고 하면, 가장 작은 숫자 1과 2을 없애면 94가 되는 예제를 보고 한 생각이었다. 그런데 4177252841에서 4개 숫자를 지우라고 하면 어떨까? (예제 3번) 작은 숫자 순서대로 4개.. 1, 2, 2, 1를 없애면 477594가 된다. 이는 정답은 775841과 다르다!!
이건 아니었다.. 그래서 다시 생각해봤다. 그랬더니 가장 큰 수가 되려면, 앞의 자리가 큰 게 중요하다는 것이 생각났다!
그래서 맨 앞부터 보면서, 그게 그 다음 숫자보다 작으면 없애는 식으로 K개를 제거하는 코드를 짰다.
그런데 처음에 그렇게만 짰더니, 11111에서 3개 숫자를 없애는 경우에는 11111이 나왔다. 54321에서 3개 숫자를 없애는 경우에도 마찬가지이고..
이처럼 쭉~ 살펴봤는데 K개를 제거하지 못했고, 결과로 나온 수는 숫자들이 다 같거나, 점점 커지는 경우 다른 처리도 필요했다. 그래서 아랫 부분을 넣었더니 맞았다!

len(ans) > N-K:
    ans = ans[:N-K]

코드 ⛄

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

l = []

def sol():
    i = 0
    cnt = 0
    while i < len(arr):
        if l:
            while l and l[-1] < arr[i]: # 앞에 작은 수 다 없애기
                l.pop()
                cnt += 1
                if cnt == K:
                    return i
        l.append(arr[i])
        i+= 1
    return len(arr)

i = sol()
ans= list(l)+arr[i:] # 중간에 리턴된 경우, 나머지 수도 더해주기

if len(ans) == N-K:
    pass
elif len(ans) > N-K:
    ans = ans[:N-K]

print(''.join(map(str,ans)))