[그리디, 스택] 코딩테스트 문제 TIL (크게 만들기) - 백준 2812번

1. 오늘의 학습 키워드

• 그리디
• 스택

---

2. 문제: 2812. 크게 만들기

• 단계: 🥇 골드 3단계
• 주제:
  • 자료 구조
  • 그리디 알고리즘
  • 스택
• 출처: 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

---

3. 문제 풀이

Step1. 문제 이해하기

주어진 문제는 N자리 숫자에서 숫자 K개를 지워서 가장 큰 수를 만드는 문제입니다.

• 주어진 숫자에서 K개의 숫자를 지우고 난후에 생성되는 가장 큰 수를 구해야 합니다.
• 이 뜻은 숫자를 구성하는 수의 위치를 변경해서는 안됩니다.

입출력은 다음과 같습니다:

• Input:
  • 첫째 줄에 N과 K가 주어집니다. (1 ≤ K < N ≤ 500,000)
  • 둘째 줄에 N자리 숫자가 주어집니다. 이 수는 0으로 시작하지 않습니다.
• Output:
  • 입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력합니다.

Step2. 문제 분석하기

숫자를 왼쪽에서 오른쪽으로 탐색하면서, 그 순간의 숫자가 이전의 숫자보다 더 크다면 이전 숫자를 지우는 방식으로 진행하면 해결할 수 있습니다.

아래 예시를 살펴보겠습니다.

• N = 4, K = 2
• 주어진 숫자: 1924

1. 1은 9보다 작습니다. 그렇기 때문에 1은 제외합니다.
2. 2는 9보다 작습니다. 따라서 2는 제외됩니다.
3. 2개를 제외했기때문에 최종 94가 나옵니다.

이 방법을 사용하기 위해선 스택 자료구조를 사용해야 합니다.

왜냐하면 현재의 숫자가 이전의 숫자보다 작으면 이전 숫자를 제거한다! 이것은 스택 자료구조의 특징인 LIFO원리에 적합하기 때문입니다.

1. 스택 사용: 숫자를 스택에 하나씩 넣고, 만약 스택의 top보다 현재 숫자가 크다면, 스택의 top을 pop하여 그 자리에 더 큰 숫자를 넣습니다.
2. 지워야 할 숫자 K개는 이 과정에서 pop된 횟수로 결정됩니다.
3. 남은 자리는 그대로 스택에 저장되어 나중에 결과를 만들 때 사용됩니다.
4. 최종 결과는 스택에 남은 숫자들을 순서대로 나열한 것이며, 남은 숫자가 K개가 되어야 합니다.

Step3. 코드 설계

1. 숫자들을 스택에 넣으면서, 그 숫자가 스택의 top보다 크면 pop을 해서 K개를 지웁니다.
2. K개를 모두 지운 후에는, 스택에 남은 숫자들을 출력합니다.
3. 남은 숫자 중에서 앞부분이 중요하므로, 불필요한 앞자리 0은 자동으로 걸러지게 됩니다.

Step4. 코드 구현

import sys
N, K = map(int, sys.stdin.readline().split())
num = sys.stdin.readline().strip()
def sol(N, K, num):
    stack = []
    idx = 0
    for n in num:
        while stack and idx < K and stack[-1] < n:
            stack.pop()
            idx += 1
        stack.append(n)
    print(''.join(stack[:N-K]))
sol(N=N, K=K, num=num)

• 코드 설명:
  • 스택을 사용한 숫자 제거:
    • stack은 숫자들을 담고 있는 리스트로, 주어진 숫자를 스택에 하나씩 넣어가며 처리합니다.
    • 각 숫자를 n이라고 할 때, 현재 스택의 top보다 더 큰 숫자가 나오면 stack.pop()을 통해 스택의 top을 제거하고, 그 자리에 더 큰 숫자를 넣습니다.
    • idx는 지운 숫자의 개수를 세는 변수로, K개를 지우면 그만큼 숫자를 지웁니다.
  • 최종 결과 계산:
    • 숫자들이 모두 스택에 쌓이면, 그 중에서 남은 숫자들이 최종 결과입니다. 지워야 할 숫자가 K개가 되었다면, 스택에 남은 숫자 중에서 처음부터 N-K개를 선택하여 결과를 만듭니다.
      • 만약 주어진 숫자가 54321와 같이 내림차순이였다면, 스택에 그대로 들어가기때문에 스택에 남은 숫자 중에서 처음부터 N-K개를 선택해야 합니다.
  • 문자열로 결과 출력:
    • 스택에 남은 숫자들을 ''.join()을 사용하여 문자열로 만들어 출력합니다.
• 시간 복잡도: 각 숫자를 한 번씩만 확인하고, 스택에 넣거나 pop하는 작업이기 때문에 전체 시간 복잡도는 $O(N)$입니다. 여기서 N은 최대 500,000까지 가능하므로, 시간 복잡도 $O(N)$은 충분히 효율적입니다.
• 결과:
  

---

4. 마무리

이번 문제는 스택과 그리디 알고리즘을 활용하여, 주어진 숫자에서 K개를 제거해 가장 큰 수를 만드는 효율적인 방법을 배울 수 있었습니다. 숫자를 순차적으로 탐색하며 스택을 사용해 현재 숫자가 이전 숫자보다 크면 제거하고 더 큰 숫자를 유지하는 방식으로, $O(N)$의 시간 복잡도로 문제를 해결할 수 있었습니다. 이를 통해 최적 선택 전략(그리디)과 스택 자료구조의 활용 능력을 향상시킬 수 있었습니다.
글 읽어주셔서 감사합니다.