[Python] 백준 2812 크게 만들기

1. 문제 링크

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

2812번: 크게 만들기

---

2. 문제 요약

• k개를 지워서 가장 큰 수 만들기

 

---

3. 아이디어 정리

• 앞에 있는 숫자가 가장 커야한다.

1. 모든 숫자를 for문을 돌려준다.
2. 리스트에 담기 마지막 숫자와 현재 숫자와 비교하여 현재 숫자가 크면 기존에 담은 수를 pop한다.

---

4. 문제 풀이

4-1. 내 풀이

import sys
"""
 k개를 지워서 얻을 수 있는 가장 큰 수 구하기 
"""
n, k = map(int, sys.stdin.readline().split()) # n자리, k개 지우기
s = sys.stdin.readline().rstrip()

# 앞에 있는 숫자가 더 커야한다.
st = list()
for i in range(n):
    # 새로들어온 수가 더 큰 경우 앞에있는것 지우기
    while st and k > 0 and st[-1] < s[i]:
        st.pop()
        k -= 1
    st.append(s[i])

print("".join(st[:len(st) - k]))

 

---

5. 결론

• 스택을 이용한다.