[백준 BOJ / Python] 24524번 아름다운 문자열

문제

S의 문자들을 골라 T를 만들 수 있다.
S에서의 순서대로 이어 붙여 새 문자열을 만드는 것을 반복하여 만들 수 있는 T의 최대 개수를 구하는 문제이다.

풀이

• S에서의 순서가 유지돼야 함을 유의한다.
• S문자열에서 차례대로 문자를 살펴보며 T를 만들 수 있는 개수를 별도의 리스트에서 셀 수 있다.
• 예를 들어 S가 adabccb 이고 T가 abc일 때, 다음과 같이 셀 수 있다.
• T에 해당하는 알파벳이 순서대로 개수가 확보되어 있는지 확인할 수 있는 리스트를 생성한다.

• S의 1번째 a 문자는 T에 포함되며 이전 문자의 개수가 무한으로 현재 문자(a) 개수보다 많기 때문에 현재 문자에 1을 더한다.

• 2번째 문자인 d는 T에 포함되지 않으므로 넘어간다.

• 3번째 문자인 a는 첫번째와 마찬가지이기 때문에 a에 1을 더한다.

• 4번째 문자인 b는 T에 포함되며, a(2) 보다 값이 작기에 1을 더할 수 있다.

• 마찬가지로 5번째 c도 조건을 만족함으로 증가시킬 수 있다.

• 하지만 6번째 c는 앞의 b(1) 보다 클 수 없기에 1을 더할 수 없다.

• 7번째 b는 T에 존재하며 앞의 a(2)보다 크기에 1을 더할 수 있다.

• 순차적으로 c까지 만들 수 있어야 하기 때문에 최종적으로 생성할 수 있는 T(abc)는 1개이다.

 

Python 코드

S = input()
t = input()
dp = [0]*(len(t)+1)
dp[0] = float("inf")
# T에 존재하는지 확인하고, 이전 단어의 위치를 빠르게 찾기 위해 사용
find_idx = {a:idx+1 for idx,a in enumerate(t)}

for s in S:
	# (조건) T에 존재하는지, 이전 단어의 수가 더 큰지 
    if s in find_idx and dp[find_idx[s]-1] > dp[find_idx[s]]:
        dp[find_idx[s]] += 1

print(dp[-1])

 

문제출처

24524번: 아름다운 문자열