백준 2812 크게 만들기

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

2812번: 크게 만들기

📌 해결순서 1 (시간초과)

일단 지워야할 숫자를 다 지우고 나면 남은 숫자는 추가해야하는 숫자들이기 때문에 지우는 방식이 아닌, 시작부터 숫자를 추가해가는 방법을 생각했다

 

# 추가하는 경우

1. 뒤에 기준 숫자보다 큰 수가 없는 경우 : 기준 숫자의 인덱스 + 남은 사이즈가 배열의 크기를 초과하지 않으면 추가

2. 뒤에 기준 숫자보다 큰 수가 있는 경우 : 그 큰 수의 인덱스 + 남은 사이즈가 배열의 크기를 초과 하면 추가

3. 비교해야하는 수의 갯수와 남은 사이즈가 같은 경우 : 남은 숫자를 모두 추가하고 종료

📌 코드

import sys
input = sys.stdin.readline

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

lst = input().rstrip()

ans = []

for i in range(n):
    while ans and k > 0:
        # 현재 스택에 추가되어있는 마지막 숫자와 추가될지 말지 결정해야하는 숫자를 비교
        if int(ans[-1]) < int(lst[i]):
            k -= 1
            ans.pop()
        else:
            break
    ans.append(lst[i])

# 주어진 숫자가 내림차순 정렬이 된 경우도 있기 때문에, n-k 만큼만 출력한다
print(''.join(ans[:n-del_cnt]))

📌 해결순서 2 (스택 자료구조 사용)

지울지 말지 결정해야하는 순간에서 최선의 결정을 내린다

 

1. 지울수 있는 숫자의 갯수가 0 보다 크고 빈 스택이 아닌 경우에서만 비교한다

2. 스택에 있는 마지막 숫자(조건을 활용해서 만들수 있는 최댓값) 이 현재 입력된 숫자보다 작다면 스택의 마지막 숫자를 꺼내고 현재 입력된 숫자를 넣는다 , 지울수 있는 숫자 -= 1

3. 반복

4. 주의해야 할 점은, 예제 입력 자체가 내림차순으로 정렬될 수 있기 때문에 n - k 만큼만 출력할 수 있도록 해야한다.

📌 코드

import sys
input = sys.stdin.readline

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

ans = []

for i in range(n):
    while ans and k > 0:
        # 현재 스택에 추가되어있는 마지막 숫자와 추가될지 말지 결정해야하는 숫자를 비교
        if int(ans[-1]) < int(lst[i]):
            k -= 1
            ans.pop()
        else:
            break
    ans.append(lst[i])
# 주어진 숫자가 내림차순 정렬이 된 경우도 있기 때문에, n-k 만큼만 출력한다
print(''.join(ans[:n-k]))