[백준/21941] 문자열 제거 - 파이썬(Python)

문제

지우고 싶은 문자열 S와 지울 수 있는 문자열 A1, A2, ..., AM이 주어진다. 문자열 Ai들은 각자 Xi라는 점수를 가진다. 이때, 문자열 S를 삭제 연산을 이용하여 모두 제거하려고 한다.

삭제 연산은 두 가지 방법이 존재하며, 원하는 만큼 여러 번에 걸쳐서 수행할 수 있다.

1. 문자열 S의 부분 문자열 중에 문자열 Ai 가 존재한다면 해당하는 부분을 지우고 Xi만큼의 점수를 얻는다(여러 부분 존재해도 한 번만 지운다).
2. 문자열 S에서 문자 하나를 지우고 점수를 1점을 얻을 수 있다.

예를 들어, 문자열 S가 "abcxyzxabc"이 있고 "abc" 문자열을 지울 경우 10점, "xyz" 문자열을 지울 경우 5점을 얻는다고 하자. 문자열을 모두 제거하여 최대 점수를 얻을 수 있는 과정은 아래와 같다.

• 문자열 S에서 문자열 "xyz" 하나를 지운다. 현재 총 얻은 점수는 5점이고 문자열 S는 "abc___xabc"가 된다. 이때, '_'는 문자가 지워진 자리를 의미한다.
• 문자열 S에서 문자열 "abc" 하나를 지운다. 현재 총 얻은 점수는 15점이고 문자열 S는 "______xabc"가 된다.
• 문자열 S에서 문자열 "abc" 하나를 지운다. 현재 총 얻은 점수는 25점이고 문자열 S는 "______x___"가 된다.
• 남은 문자들을 하나씩 지운다. 현재 총 얻은 점수는 26점이고 문자열 S는 빈 문자열이 된다.

문자열을 모두 제거하여 얻을 수 있는 최대 점수는 26점이다. 이보다 더 얻을 수 있는 점수는 없다.

삭제 연산을 이용하여 문자열 S을 지우려고 할 때 얻을 수 있는 최대 점수는 몇 점인지 계산하자.

입력

첫 번째 줄에는 문자열 S이 주어진다.

두 번째 줄에는 지울 수 있는 문자열 개수 M이 주어진다.

세 번째 줄부터 M+2 줄까지 문자열 Ai와 점수 Xi이 공백으로 구분되어 주어진다.

출력

문자열 S를 모두 제거하여 얻을 수 있는 점수를 출력하자.

제한

• 입력으로 주어지는 문자열을 모두 알파벳 소문자로 구성되어 있다.
•  1≤|S|≤1,000
•  1≤M≤100
•  1≤|Ai|≤100
•  1≤Xi≤10,000

21941번: 문자열 제거

반응형

문제 풀이

문제를 풀 때 유의했던 점

1. 점수가 문자열 길이보다 적을 경우 문자 하나를 지우고 점수 1점을 얻는 것이 이득이다.
2. 점수가 큰 문자열을 먼저 제거한다.
   • 이때, 문자열의 길이와 점수를 나눠 비율을 구해서 비교하도록 한다.
3. replace를 통해서 문제와 같이 문자 제거 후 빈 문자를 만들어 주었다.
   • 문자열 변경 시 횟수를 지정해서 점수가 계산되도록 했다.

DP문제로 분류되어 있었지만, 그리디 알고리즘으로도 풀이가 가능한 것 같았다. 

import heapq
input = __import__('sys').stdin.readline


def del_chr(str, cnt):
	for i in range(len(str)-1):
		if str[i] != "_":
			cnt += 1
			str = str.replace(str[i], "_", 1)
	return cnt


s = input()
M = int(input())
heap_A = []
heap_X = []
score = 0
for _ in range(M):
	A, X = map(str, input().split())
	la = len(A)
	ix = int(X)
	heapq.heappush(heap_A, (-(ix/la), A))
	heapq.heappush(heap_X, (-(ix/la), int(X)))
while heap_A:
	_, a = heapq.heappop(heap_A)
	_, x = heapq.heappop(heap_X)
	if x > len(a):
		while a in s:
			score += x
            s = s.replace(a, "_", 1)
score += del_chr(s, 0)
print(score)