BOJ - 2812. 크게 만들기

문제

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

입력

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

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

출력

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

예제 입력 1

4 2 1924

예제 출력 1

94

---

풀이

그리디 알고리즘과 자료 구조를 사용해서 해결할 수 있는 문제

Deque를 사용 (Deque는 스택+큐의 성질을 갖는다)

1. 데크가 비어있을 경우, input[i]를 맨 끝에 집어 넣는다.
2. 데크가 비어있지 않을 경우, 데크의 맨 끝 요소와 input[i]에 대해 비교를 한다.
3. 데크의 맨 끝 요소가 작을 경우, 데크에서 없앤다.
4. input[i] 를 맨 끝에 집어 넣는다.

예시

(1) N = 5, K = 2, input = 89123

처음에는 deque가 비어있으므로 8을 맨 끝에 집어넣습니다.

그리고 input[1] = 9과 deque에 맨 끝과 비교해 봅시다. deque에 맨 끝은 8이므로 9보다 작습니다. 따라서 deque에서 8을 삭제하고 9를 추가합니다.

input[2] = 1입니다. deque에 맨 끝인 9보다 작으므로 1을 바로 추가합니다.

input[3] = 2입니다. deque에 맨 끝은 1이므로 1을 삭제합니다. 삭제 후,  deque에 맨 끝은 9이므로 2보다 큽니다. 따라서 삭제 과정을 종료하고, 2를 추가합니다.

input[4] = 3입니다. deque에 맨 끝과 비교를 하려고 하였으나, 이미 2번을 지운 상태이므로 삭제 과정을 거치지 않고 바로 3을 추가합니다.

그림에서 볼 수 있듯이, 답은 923이 됩니다.

하지만, K만큼 삭제하기 전에 위에 과정이 끝나는 경우도 있습니다.  아래 예시를 통해 알아봅시다.

(2) N = 5, K = 2, input = 55555

숫자가 이렇게 중복되어 나타나는 경우, 삭제하는 과정 없이 단순히 deque에 추가만 된다는 사실을 알 수 있습니다. 따라서 이러한 경우에는 deque.size() - K만큼만 출력을 해 주어야 합니다.