백준 24524: 아름다운 문자열 [Kotlin 코틀린 / 그리디 / 문자열]

백준 24524: 아름다운 문자열

😋 문제 분석

문자열 S의 길이는 백만까지 가능한 것에 비해 아름다운 문자열 T의 길이는 최대 26이다.
또한 문자열 T에는 같은 문자가 존재하지 않는다는 조건이 있다.
S에 속한 문자열의 순서를 유지하며 T를 만들어야 한다.

✅ 문제 풀이

아름다운 문자열을 만드는 데 가장 중요한 것은
문자열을 이루는 문자의 순서가 지켜져야 한다는 것이다.
예시로 aabb에서는 ba가 만들어 질 수 없다.
모든 a가 b의 뒤가 아니라 앞에 존재하고 있기 때문이다.

그럼 순서를 파악하면서 문자열을 완성시켜 나가는 방법을 고민해보자.
위 예시의 문자열을 탐색하는 중 a를 만났다면, 어떤 것을 확인해야 될까?
지금까지 앞에 b가 있었는지를 확인해야 된다.
그럼 b를 만났다면?
혹시 뒤에 a가 나올지 모르니 b가 앞에 존재한다는 증거를 남겨야 된다.
결국 (첫번째 문자를 제외한) 문자들의 바로 앞에 존재하는 문자가 이전에 있었는 지만 확실하게 파악하면 될 듯하다.

다양한 방식으로 파악할 수 있겠지만,
나는 문자열 T의 문자들이 차지하는 위치를 기반으로 파악해보았다.
우선 T에 속한 문자들의 위치(인덱스)를 Map에 기록한다.

val tIdx = buildMap { T.forEachIndexed { index, c -> put(c, index) } }

그리고 각 문자의 존재 여부를 IntArray에 기록해보겠다.
ab를 만들어야 하는데 aabb와 같은 input이 있을 수 있기 때문에
개수를 셀 수 있도록 IntArray에 기록한다.
T에 속한 문자들의 개수를 셀 것이므로 T의 길이를 크기로 설정하면 된다.

val checked = IntArray(T.length) { 0 }

이제 문자열 S을 선형 탐색 해보자.

for (s in S) {
	...
}

S에는 T에 속하지 않는 문자도 포함되어 있을 것이다.
T에 포함되는 문자만 상대하자.

for (s in S) {
	if (s in tIdx) { // T에 속한 문자들은 tIdx의 key로 등록되어 있다.
    	...
    }
}

아름다운 문자열 T에 속하는 문자 s를 만났다면,
그 문자 s 보다 앞서야 되는 문자가 존재하는지 확인해보자.
만약 s가 문자열 T의 가장 맨 앞 문자라면 그냥 개수만 세자.

for (s in S) {
	if (s in tIdx) { 
    	val idx = tIdx[s] ?: -1
        
        if (idx == 0) { // 맨 앞 문자라면
        	checked[idx]++ // 그냥 개수만 카운트
        } else if (idx > 0) { // 앞에 존재해야 하는 문자가 있다면
        	...
        }
    }
}

맨 앞 문자가 아니라 앞에 존재해야 되는 문자가 있다면,
그게 존재하는지 (한번이라도 카운트 됐는지) 확인해보고,
존재한다면 차감한 뒤, 자신의 카운트를 높이자.

for (s in S) {
	if (s in tIdx) { 
    	val idx = tIdx[s] ?: -1
        
        if (idx == 0) { // 맨 앞 문자라면
        	checked[idx]++ // 그냥 개수만 카운트
        } else if (idx > 0) { // 앞에 존재해야 하는 문자가 있다면
        	if (checked[idx - 1] > 0) {
            	checked[idx - 1]-- // 차감해주고
                checked[idx]++ // 다음 문자는 카운트 한다.
            }
        }
    }
}

이런 식의 로직으로 진행하면 결국
순서를 지키면서 문자열 T의 마지막 단어까지 도달하게 될 것이다.
즉, 끝에 가서는 checked[T.length - 1]의 값을 상승시킨다.
결국 checked.last()의 값은 완성된 문자열의 개수나 다름없다.
출력하면 정답.

...
print(checked.last())