(Python/🥇3)백준알고리즘 2812번 : 크게 만들기

 

문제 바로가기 

백준 알고리즘 크게 만들기

문제:

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

입력:

 

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000) 둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

출력:

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

 

 

풀이 :

 

처음 문제 이해를 잘 못했다.

 

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

N, K = map(int,sys.stdin.readline().split(" "))
num = list(sys.stdin.readline())
stack = []

temp =""
while len(temp) < N-K:
    now = num.popleft()
    if all(now >= i for i in num):
        temp += str(now)
    else:
        num.append(now)
print(temp)

 

그냥 가장 큰 값을 만들려고 했다 ..

 

다시 풀었다.

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

N, K = map(int,sys.stdin.readline().split(" "))
ra = N-K
num = list(sys.stdin.readline())
stack = []


for i in range(N):
    while K > 0 and stack and stack[-1] < num[i]:
        stack.pop()
        K -= 1
    stack.append(num[i])
print(''.join(stack[:ra]))

 

앞에서 부터 출발하면서 

지울 수 있는 카운트가 있으면서 스택이 비어있지 않으며 스택 마지막에 들어 간 값이 다음  num과 비교해서 작으면 넣으주고 아니면 

stack에서 빼주고 지금 숫자를 넣어준다.

 

4 2 1924 일때

['1']
['9']
['9', '2']

['9', '4']

요런식 으로 나오게된다.