[PS] BOJ 24524 / 아름다운 문자열
![[PS] BOJ 24524 / 아름다운 문자열](/content/images/size/w2000/2025/12/--------------1--1.png)
문제 링크: https://www.acmicpc.net/problem/24524
풀이
단계 별로 생각하기
문자열 $S$에 포함된 알파벳들을 기존 순서를 유지한 채 골라서 문자열 $T$를 구성해야 합니다. 이때, $S$의 각 문자는 최대 한 번만 사용할 수 있습니다.
$T$를 구성하기 위해 임의의 문자 $x$가 필요할 때, $S$에서 가장 앞에 위치한 $x$를 먼저 고르는게 항상 최선의 답이 됩니다. 따라서, $S$를 한번 읽으면서 알파벳 별로 등장한 위치를 정리하고, 그 정보를 토대로 $T$의 각 알파벳을 앞에서부터 하나씩 골라 가능한 대로 만들면 됩니다.
1) $S$에서 알파벳 찾아 정리하기
$S$를 한번 읽으면서 각 알파벳 소문자가 등장한 위치를 알파벳 별로 정리합니다.
word_info = {chr(97 + c): deque() for c in range(26)}
for i, c in enumerate(S):
word_info[c].append(i)S에서 등장한 알파벳의 위치 정보 기록하기
2) $S$로 $T$ 구성하기
앞서 $S$의 알파벳의 위치 정보를 정리한 Map을 토대로 $T$를 구성합니다.
$T$를 구성할 때, 각 알파벳을 앞에서부터 하나씩 골라 선택하는 방식을 사용합니다. 이 때, 항상 다음 알파벳의 위치를 미리 확인해 다음 알파벳이 현재 알파벳의 위치보다 더 앞에 위치한다면 문제 조건 ($S$에서 순서대로 가져오기)에 맞지 않으므로 다음 알파벳의 다음 위치를 반복해서 찾아 조건에 맞게 구성해주면 됩니다.
cnt = 0
can_make = True
while can_make:
for t_idx in range(len(T)):
c = T[t_idx]
if len(word_info[c]) == 0: # T의 문자가 S에 없는 경우
can_make = False
break
pos = word_info[c].popleft()
if t_idx < len(T) - 1:
next_c = T[t_idx + 1]
if len(word_info[next_c]) == 0: # 다음 차례의 문자가 S에 없는 경우
can_make = False
break
while word_info[next_c][0] <= pos: # 다음 차례의 문자가 현재 문자보다 앞에 있을 경우 조건에 맞지 않는다.
# 이 경우 next_c의 이번 요소는 조합에 T의 구성에 사용될 수 없으니 버리고 계속 탐색한다.
word_info[next_c].popleft()
if len(word_info[next_c]) == 0: # 다음 차례의 문자가 S에 없는 경우
can_make = False
break
else: # T의 모든 문자를 한 차례 구성한 경우에만 진입하는 구문
cnt += 1
print(cnt)S로 T를 가능한 만큼 구성하기
전체 코드
from collections import deque
input = open(0).readline
S = input().rstrip()
T = input().rstrip()
word_info = {chr(97 + c): deque() for c in range(26)}
for i, c in enumerate(S):
word_info[c].append(i)
cnt = 0
can_make = True
while can_make:
for t_idx in range(len(T)):
c = T[t_idx]
if len(word_info[c]) == 0: # T의 문자가 S에 없는 경우
can_make = False
break
pos = word_info[c].popleft()
if t_idx < len(T) - 1:
next_c = T[t_idx + 1]
if len(word_info[next_c]) == 0: # 다음 차례의 문자가 S에 없는 경우
can_make = False
break
while word_info[next_c][0] <= pos: # 다음 차례의 문자가 현재 문자보다 앞에 있을 경우 조건에 맞지 않는다.
# 이 경우 next_c의 이번 요소는 조합에 T의 구성에 사용될 수 없으니 버리고 계속 탐색한다.
word_info[next_c].popleft()
if len(word_info[next_c]) == 0: # 다음 차례의 문자가 S에 없는 경우
can_make = False
break
else: # T의 모든 문자를 한 차례 구성한 경우에만 진입하는 구문
cnt += 1
print(cnt)solution.py