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

		2022 성균관대학교 프로그래밍 경진대회 Open Contest 풀이
A		[BOJ 24523] 내 뒤에 나와 다른 수
B		[BOJ 24524] 아름다운 문자열
C		[BOJ 24525] SKK 문자열
D		[BOJ 24526] 전화 돌리기
E		[BOJ 24527] 이상한 나라의 갈톤보드

1. 문제

$24524$. 아름다운 문자열 (2022 성균관대학교 프로그래밍 경진대회 Open Contest B번)

백준 24524번 - 아름다운 문자열 (https://www.acmicpc.net/problem/24524)

2. 풀이

문자열 $T$에 있는 모든 문자를 순서대로 골라내야 한다. 따라서 해당 문자들을 순서에 맞게끔 최대한 왼쪽에서 골라내는 것이 최적이다.

반례로 ‘$S=ababcc,\, T=abc$’가 있다. 실제로는 $T$를 두 개 만들 수 있음에도 불구하고, 첫번째 $a$를 고르고 네번째 $b$(두번째가 아닌)를 고르고 뒤에 $c$를 골라버리면, $T$를 한 개 만들고 $S=bac$가 되어버려 $T$를 더 이상 만들 수 없게 되어 버린다.

각각의 문자에서 최대한 왼쪽의 수를 뽑기 위해, $S$를 왼쪽부터 탐색하면서 각각의 문자열 queue에 해당 문자가 나타나는 index를 집어넣는다. 그럼 그림의 표가 완성된다.

$T=abc$이므로, $abc$를 완성시키되 $index\;of\;‘a’ $ $\lt index\;of\;‘b’ $ $\lt index\;of\;‘c’$ 조건을 만족하도록 각각의 queue에서 index를 뽑아낸다. 그림에서 index의 조건에 부합하지 않는 수는 지나가버리는 것을 볼 수 있다.

$a$에서 $1$을 뽑고 $b$에서 $2$를 뽑았다. 그런데 $c$ queue의 front index는 $2$보다 작은 $0$이다. 따라서 그냥 지나가서 다음 수를 검사하고 $2 \lt 7$이므로 $7$을 뽑아 하나의 abc가 완성된다.

한 번 검사하고 끝나는 것이 아니라 완성되는 수를 찾아 while문으로 계속 검사해야 한다. 이는 코드를 통해 확인할 수 있다.

어떤 queue에서 수를 더 이상 뽑을 수 없다면, 더 이상 $T$를 만들 수 없으므로 탐색을 종료한다.

3. 채점 결과

4. 회고

.

5. 코드