크게 만들기

출처 : 백준 #2821

시간 제한	메모리 제한
1초	128MB

---

문제

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

풀이

생각 및 풀이 설명

• 원래 생각

  • 원래는 k만큼 for문을 돌면서, n만큼 이중 for문을 돌려서 다음 원소가 현재 인덱스의 원소보다 크다면, 자릿수가 큰데 작은 숫자이므로 없애주고 break를 하여 for문을 빠져나온다.
  • 그렇게 k번 반복하면 된다.
  • 하지만 이 풀이는 시간초과가 나온다.
  • 반례는 다음과 같다. (9999999999999999999999...99321)
  • 이런식으로 큰 숫자가 앞에 계속 존재를 하는 경우 k번 for문을 돌 때 n만큼 반복을 해야한다.
  • 게다가 k가 n만큼 커진다면 O(n^2)에 가까운 시간 복잡도가 된다.

• 개선된 풀이

  • 오히려 for문으로 k만큼 돌린다기보다는 k는 count의 개념으로 쓰고, n만큼 for문을 돌린다.
  • 그러면서 stack의 마지막 원소와 현재 인덱스의 숫자를 비교하며, 작다면 pop을 해준다. (while문을 통해 k개의 원소를 제거할 수 있을 때까지 반복)
  • for문마다 현재 인덱스의 원소를 stack에 넣어준다.

• 사실 개선된 풀이를 온전히 내 힘으로 생각하지 못했다. 순차적으로 탐색을 해야한다고 나도 모르게 강박관념을 가져서 그랬던 것 같다.

• 조금만 더 자료구조에 대한 관심을 갖고 시간복잡도를 줄이려고 노력해야겠다.

python code

# 백준 2812번 크게 만들기
from sys import stdin
input = stdin.readline

n, k = map(int, input().split())
number = list(map(int, input().rstrip()))
stack = []
for i in range(n):
    while len(stack)>0 and stack[-1] < number[i] and 0 < k:
        stack.pop()
        k -= 1
    stack.append(number[i])

while 0 < k:
    stack.pop()
    k -= 1

result = "".join(map(str, stack))
print(result)