[PS] BOJ 32767 / 문자열 줄이기

문제 링크: https://www.acmicpc.net/problem/32767

Thumbnail: Photo by Diya Pokharel / Unsplash

처음에 브루투 포스 방식으로 풀었는데, 당연하게도 시간 초과를 맞닥뜨렸습니다..

문제

알파벳 소문자로 구성된 길이 \(N\)의 문자열 \(S\)가 주어진다.

\(S\)에 대하여 문자열 줄이기를 \(M\)번 시행한다. 문자열 줄이기의 과정은 다음과 같다.

•  \(S\)에 포함된 문자 중 사전 순으로 가장 앞서는 문자를 하나 제거한다. 이때 가장 앞서는 문자가 여러 개일 경우 그 중 제일 앞에 위치한 문자를 하나 제거한다.

문자열 줄이기를 \(M\)번 시행한 뒤의 문자열 \(S\)를 구하자.

입력

첫째 줄에 1,000보다 작거나 같은 자연수 \(N\)이 주어진다.

출력

첫 번째 줄에 두 정수 \(N\)과 \(M\)이 공백으로 구분되어 주어진다. \((0 \le M \less N \le 3 \times 10^5)\)

두 번째 줄에 알파벳 소문자로 구성된 길이 \(N\)의 문자열  \(S\)가 주어진다.

풀이

문자열을 정렬하고, 하나씩 지워가며... 하는 풀이로는 시간 초과가 발생한다!
하지만, 지워야 하는 문자를 파악해두고 출력할 때 이를 고려한다면 어떨까?

먼저, \(S\)의 각 문자가 몇개씩 들어있는지 개수를 센다.

이후, 최대 M개까지 문자를 지운다는 점을 고려해, \(S\)의 각 문자들을 몇 개 제거해야할 지 기록한다. 만약 문자 \(c\)가 \(i\)개 있다면, \(i\)가 \(M\)보다 작다면 \(c\)를 아예 삭제하고, 그렇지 않다면 \(M\)개 만큼만 삭제하면 된다. 이를 \(S\)의 각 문자들을 사전상 빠른 순서대로 반복하며 진행한다.

마지막으로, 미리 기록해 둔 정보를 토대로 문자열의 각 문자를 출력할지 말지 판단하면 된다.

코드

from sys import stdin

N, M = map(int, stdin.readline().strip().split())
S = stdin.readline().strip()

# S를 이루는 각 문자의 개수를 센다.
char_count = {}
for c in S:
    if c not in char_count:
        char_count[c] = 1
    else:
        char_count[c] += 1

# 지워야 하는 문자들을 미리 기록해 둔다.
deleted = {}
for c in sorted(char_count):
    if char_count[c] > M:
        deleted[c] = M
        break
    else:
        deleted[c] = char_count[c]
        M -= char_count[c]

# 미리 기록해 둔 정보를 토대로, 문자들을 지워서 출력한다.
for c in S:
    if c in deleted:
        if deleted[c] > 0:
            deleted[c] -= 1
        else:
            print(c, end="")
    else:
        print(c, end="")
print()