200973번: Uddered but not Herd

문제 출처 : https://www.acmicpc.net/problem/20973

 

언어 : Kotlin

 

문제 설명 :

A little known fact about cows is that they have their own version of the alphabet, the "cowphabet". It consists of the 26 letters 'a' through 'z', but when a cow speaks the cowphabet, she lists these letters in a specific ordering that might be different from the order 'abcdefghijklmnopqrstuvwxyz' we are used to hearing.

To pass the time, Bessie the cow has been humming the cowphabet over and over again, and Farmer John is curious how many times she's hummed it.

Given a lowercase string of letters that Farmer John has heard Bessie say, compute the minimum number of times Bessie must have hummed the entire cowphabet in order for Farmer John to have heard the given string. Farmer John isn't always paying attention to what Bessie hums, and so he might have missed some of the letters that Bessie has hummed. The string you are told consists of just the letters that he remembers hearing.

 

입력 :

The first line of input contains the 26 lowercase letters 'a' through 'z' in the order they appear in the cowphabet. The next line contains the string of lowercase letters that Farmer John heard Bessie say. This string has length at least 1 and at most 1000

 

출력 :

Print the minimum number of times Bessie must have hummed the entire cowphabet.

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 512MB

 

입출력 예 :

입력	출력
abcdefghijklmnopqrstuvwxyz mood	3

 

풀이 : 

소가 흥얼거린 알파벳 26개와 농부가 들은 단어를 토대로 인덱스 비교.

소의 알파벳을 Map에 담고, 농부의 단어를 순회하며 현재 위치와 Map의 단어 위치를 비교한다.

 

첫 시작시 현재 위치는 -1로 초기화 해두고, 농부의 단어를 순회할때 해당 순번의 문자의 소 알파벳에서의 위치와 현재 위치를 비교하여 현재 위치가 해당 순번보다 작거나 같을 때 cnt++ 시킨다.

 

예제 1번의 경우

abcdefghijklmnopqrstuvwxyz

mood

 

m은 소 알파벳에서 12번째 위치.

현재 위치는 -1부터 시작하므로 소가 m을 흥얼거릴때까지의 총 반복 횟수는 1번이다.

 

o로 넘어가면, 소 알파벳에서 14번째 위치.

현재 위치는 m의 위치를 이어받아 12부터 시작하므로 위치상 뒤에 존재하지 않고 더 진행해야 o를 찾을 수 있기에 총 반복 횟수는 1에서 증가하지 않는다.

 

하지만 2번째 o의 경우,

현재 위치 14번째, 소 알파벳에서의 o도 14번째이므로 한번 더 흥얼거려야 o를 들을 수 있다.

그렇기에 총 반복횟수는 2

 

마지막 문자 d의 경우,

d의 소 알파벳에서의 위치는 3번째 위치.

현재 위치는 14번째이므로 흥얼거림을 끝내고 새로 흥얼거려야 d를 들을 수 있다.

그렇기에 총 반복횟수는 3.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val cowphabet = readLine()
    val heard = readLine()
    
    val posMap = mutableMapOf<Char, Int>()
    for ((i, c) in cowphabet.withIndex()) {
        posMap[c] = i
    }
    
    var cnt = 1
    var curPos = -1
    for (c in heard) {
        val pos = posMap[c]!!
        
        if (pos <= curPos) cnt++
        curPos = pos
    }
    
    bw.write("$cnt")
    bw.flush()
    bw.close()
}