백준 2812 크게 만들기 (파이썬)

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

2812번: 크게 만들기

풀이

숫자를 지웠을때 만들수있는 수 가운데 가장 큰 수를 만들어야 하는 문제이다.

이 문제는 그리디 문제로 일종의 규칙을 발견하는 것이 중요하다.

입력 예제로 주어진 값들을 직접 지우다 보면 다음과 같은 규칙들을 발견할 수 있다.

순서	예제 입력1	예제 입력2	예제 입력3
1	1924	1231234	4177252841
2	924	231234	477252841
3	94	31234	77252841
		3234	7752841
			775841

값을 지우다 보면 idx의 값과 idx+1의 값을 서로 비교해서 만약 idx+1의 값이 더 크다면 idx의 값을 지우는 규칙을 발견 할 수 있다.

추가로 내림차순일 경우는 위의 규칙을 적용하여도 가장 작은 값을 찾을 수 없다.

그렇기에 값을 끝까지 확인하였는데도 아직 지워야 하는 횟수를 전부 채우지 못하였다면 뒤에서 해당 횟수만큼 없애면 된다.

(규칙을 통해서 뒤에 있는 idx의 값보다 앞의 있는 idx의 값이 작음을 알수있기 때문이다.)

 

코드

처음에는 스택을 사용하지않고 문자열로 구현했지만 시간 초과가 나왔다.

import sys
input = sys.stdin.readline

N, K = map(int, input().split(" "))
data = list(map(int, list(input()[:-1])))

idx = 0
while K > 0 and idx < N-1:
    if data[idx] < data[idx+1]:
        del data[idx]
        K -= 1
        N -= 1
        idx = 0
        continue
    
    idx += 1
    

if K > 0:
    data = data[:-K]
    
print(''.join(map(str,data)))

다음은 스택을 이용한 코드이다.

import sys
input = sys.stdin.readline

N, K = map(int, input().split(" "))
datas = input().rstrip()

idx = 0
st = []
for data in datas:
    while st and st[-1] < data and K > 0:
        st.pop()
        K -= 1
    st.append(data) 
    

if K > 0:
    st = st[:-K]

print(''.join(st))