문제 풀이
그리디
Tpos = T에서 해당 알파벳이 몇 번째 인덱스인지
count = S의 순서대로 T를 만들도록 뽑으면 해당 문자가 몇개 뽑힐 수 있는지
idx = S에서 현재 문자가 T에서 몇 번째 인덱스인지
S에서 문자를 순서대로 뽑아 T를 만드려면 현재 문자가 T에 있을 때 T에 존재하는 이전 문자가 뽑혔는지 확인해야 함
S에서 T에 존재하는 문자가 뽑힌 횟수를 세놓으면 이전 문자가 이미 뽑혀있으면 현재 문자가 뽑힌 갯수보다 많으므로 확인이 가능함
매번 count 배열에 갯수를 확인할 때 해당 알파벳이 T에서 몇 번째 인덱스인지 확인해야 함
T가 서로 다른 알파벳으로 주어진다고 했으므로 알파벳마다 몇 번째 인덱스인지 미리 구해놓으면 확인이 편함
Tpos 배열을 만들어 알파벳마다 몇 번째 인덱스인지 저장하면 되는데 S에 존재하는 알파벳이 T에 없을 수도 있으므로 초깃값을 -1로 설정하고 T의 문자 하나마다 인덱스를 저장함
S에서 문자 하나씩 확인하며 인덱스를 Tpos 배열에서 확인해 idx에 저장함
idx가 -1이라면 T에 존재하지 않으므로 넘김
0이라면 첫 문자이므로 조건 없이 뽑을 수 있으므로 count[idx]를 1 증가시킴
-1이나 0이 둘다 아니라면 이전 문자를 확인해야 하므로 count[idx - 1]이 count[idx]보다 클 때만 count[idx]를 1 증가시킴
count[T.length - 1]이 T의 마지막 문자가 뽑힌 횟수고 이 값이 T가 뽑히는 횟수이므로 출력하면 정답
풀이 설명
문자열 S와 서로 다른 문자로 구성된 문자열 T가 있을 때 문자를 S에서의 순서대로 뽑아 문자열 T를 몇 개 만들 수 있는지 구하는 문제이다.
문자열 T가 순서가 정해져 있으므로 문자열 S에서 뽑은 문자가 문자열 T의 일부가 되려면 현재 뽑은 문자보다 앞에 있어야 하는 문자가 이미 먼저 뽑혀있어야 한다.
문자열 T가 서로 다른 문자로 이루어져 있으므로, 문자마다 뽑힌 갯수를 세면 이전 문자와 현재 문자가 뽑힌 갯수를 비교해 먼저 뽑혀있는지 확인할 수 있다.
문자열 S와 T가 모두 소문자 알파벳으로만 이루어진다고 했으므로 문자가 알파벳마다 몇 번째 순서인지 미리 찾아놓으면 매번 찾을 필요 없이 해당 문자가 몇 번째 문자인지 쉽게 찾을 수 있다.
이에 따라 문제를 풀기 위해 알파벳의 순서를 Tpos, S에서 뽑은 문자의 갯수가 몇 개인지를 count에 저장한다.
S에 존재하는 알파벳이 T에 존재하지 않을 수 있으므로 Tpos 배열의 초깃값을 -1로 초기화한다. 또한 Tpos의 인덱스는 알파벳의 순서로 사용하기 위해 해당 알파벳을 문자 'a'로 뺀 값을 인덱스로 쓴다.
그 이후에 T의 문자를 하나하나 확인하면서 문자를 Tpos 배열의 인덱스, 해당 문자가 T의 몇 번째 인덱스에 있는지를 값으로 저장한다.
마지막으로 T가 몇 개 뽑힐 수 있는지 확인하기 위해 S의 문자 하나하나마다 T에서의 인덱스를 Tpos 배열에서 확인해 idx에 저장한다.
그 이후에 idx가 -1이라면 T에 존재하지 않는 알파벳이므로 넘기고, 그게 아니라면 해당 문자가 뽑힐 수 있는지 확인해야 한다.
만약 idx가 0이라면 T의 첫 문자이므로 이전 문자가 없으므로 바로 뽑힐 수 있다. 따라서 count[idx]를 1 증가시켜 해당 문자를 뽑으면 된다.
0이 아니라면 이전 문자가 먼저 뽑혔는지 확인해야 하므로 count[idx - 1]이 count[idx]보다 클 경우에만 count[idx]를 1 증가시켜 문자를 뽑는다.
그렇게 모든 문자를 처리하면 count[T.length - 1]에 T의 마지막 문자가 몇 번 뽑혔는지 확인할 수 있고 이는 T가 뽑히는 갯수와 동일하므로 출력하면 정답이 된다.
소스 코드
fun main() = System.`in`.bufferedReader().run {
val S = readLine()
val T = readLine()
val Tpos = IntArray(26){-1}
for(j in 0 until T.length){
Tpos[T[j] - 'a'] = j
}
val count = IntArray(T.length)
for(i in 0 until S.length){
val idx = Tpos[S[i] - 'a']
if(idx != -1){
if(idx == 0){
count[idx]++
} else if(count[idx - 1] > count[idx]){
count[idx]++
}
}
}
println(count.last())
}