문제 설명
•
알파벳 소문자로 구성된 길이 N의 문자열 S에 대하여 문자열 줄이기를 M번 시행한 뒤의 문자열 S를 출력하는 문제
◦
S에 포함된 문자 중 사전 순으로 가장 앞서는 문자를 하나 제거한다.
◦
이때 가장 앞서는 문자가 여러 개일 경우 그 중 제일 앞에 위치한 문자를 하나 제거한다.
예제 입력/출력
•
입력1
5 3
acdab
Plain Text
복사
•
출력1
cd
Plain Text
복사
제약 조건
•
문제 풀이
접근1 브루트 포스 (완전 탐색) -
•
접근2 그리디 -
◦
접근 방식
1.
주어진 문자열 S에서 각 알파벳이 몇 번 등장하는지 세어둔다.
2.
알파벳 순서대로 a → b → c → … 순으로 가능한 만큼 제거한다.
•
예를 들어, M이 3이라면
◦
a가 2개 있다면 모두 제거
◦
b가 1개 있다면 제거
◦
c부터는 더 이상 제거할 필요 없음
3.
원래 문자열을 한 번 순회하면서 삭제되지 않은 문자들만 출력한다.
풀이 코드
from collections import Counter
N, M = map(int, input().split())
S = input()
count = Counter(S)
delete = {c: 0 for c in count}
# 삭제해야 할 문자 개수 계산
for c in sorted(count):
if count[c] > M:
delete[c] = M
break
else:
delete[c] = count[c]
M -= count[c]
# 출력
for s in S:
if delete[s] > 0:
delete[s] -= 1
else:
print(s, end="")
Python
복사
