백준 / 2812번 크게 만들기 - 스택 / Python 파이썬

 

*문제 출처는 백준에 있습니다.

문제 제목: 크게 만들기

문제 사이트: https://www.acmicpc.net/problem/2812

문제

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

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)

둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

출력

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

예제 입력 1 복사

4 2
1924

예제 출력 1 복사

94

예제 입력 2 복사

7 3
1231234

예제 출력 2 복사

3234

예제 입력 3 복사

10 4
4177252841

예제 출력 3 복사

775841

---

나의 풀이

# Python 풀이

N, K = map(int, input().split())  # N: 숫자의 자리 수, K: 제거할 숫자 개수
s = input()  # 숫자 문자열

arr = []  # 결과 숫자를 저장할 스택 역할의 리스트

for i in range(len(s)):
    # K가 남아 있고, arr이 비어있지 않으며, 현재 숫자가 스택 top보다 클 경우
    # 더 큰 수를 만들기 위해 스택의 작은 수 제거
    while K > 0 and arr and arr[-1] < int(s[i]):
        arr.pop()
        K -= 1
    arr.append(int(s[i]))  # 현재 숫자를 스택에 추가

# 모든 순회를 끝냈지만 아직 K개를 다 제거하지 못했으면,
# 뒤에서부터 K개를 잘라냄 (큰 수 만들기 위함)
if K > 0:
    print(''.join(map(str, arr[:-K])))  # 뒤에서 K개 제거하고 출력
else:
    print(''.join(map(str, arr)))  # 그대로 출력

---

알고리즘 핵심 (그리디 + 스택)

• 앞에서부터 숫자를 보면서, 지금보다 더 큰 숫자가 나오면 이전 숫자를 버림
• 이걸 K번만 할 수 있음 → 제거 횟수가 제한되어 있음
• 스택을 이용해서 처리:
  • 현재 숫자가 스택 top보다 크면, 스택에서 pop하고 K -= 1
  • 아니면 그냥 push

 

예시

number = "1924", K = 2 

과정:

1. '1' → 스택에 추가 → [1]
2. '9' > 1 → 1 제거, K=1 → [9]
3. '2' → 스택에 추가 → [9,2]
4. '4' > 2 → 2 제거, K=0 → [9,4]

결과: 94

 

---

※ 알아야 할 것

• 문자열 길이는 최대 10^6 → 완전탐색 불가!
• 숫자 간 순서를 바꾸면 안됨
• 스택에는 숫자가 아닌 인덱스가 아닌 값을 넣어도 됨 (문자 또는 int)

나는 스택이 약한가보구나