28432번: 끝말잇기

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

28432번: 끝말잇기

언어 : Kotlin

 

문제 설명 :

끝말잇기는 단어를 중복하지 않고 단어의 맨 끝 글자에 이어서 말하는 놀이입니다. 끝말잇기 기록은 단어들의 나열로 이루어집니다. 올바른 끝말잇기 기록은 각 단어의 마지막 글자가 다음 단어의 첫 글자이며, 단어가 중복되어서 나타나면 안 됩니다.

끝말잇기 기록이 주어지는데, 하나의 기록은 “?”로 가려진 채로 들어옵니다. “?”에 들어갈 수 있는 문자열들의 후보가 주어질 때, 올바른 끝말잇기 기록을 만드는 “?”에 들어갈 문자열을 출력하세요.

 

입력 :

첫 줄에 끝말잇기 기록의 길이 N 이 주어집니다. (1 \le N \le 100) 둘째 줄부터 다음 N개의 줄에는 끝말잇기의 기록 S_1, \cdots, S_N이 한 줄에 하나씩 주어집니다. 여기서, 하나의 S_i는 “?” 로 주어집니다. 나머지 S_i는 길이 2 이상 10 이하의 영어 소문자로 이루어진 문자열입니다.

다음 줄에 후보 단어의 개수 M이 주어집니다. (1 \le M \le 100)

다음 M개의 줄에는 후보 단어 A_1, \cdots, A_M이 주어집니다. 

A_i는 길이 2 이상 10 이하의 영어 소문자로 이루어진 문자열입니다. A_1, \cdots, A_M은 서로 다릅니다.

문제의 답이 정확히 하나인 경우만 입력으로 주어집니다.

 

출력 :

“?”에 들어갈 수 있는 문자열을 후보 단어인 
A_1, ..., A_M 중에서 하나 찾아서 출력하세요.

 

제한 사항 :

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

 

입출력 예 :

입력	출력
5 charlie echo ? romeo oscar 3 alfa oscar or	or

 

풀이 : 

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 s = Array<String>(readLine().toInt()) { readLine() }
    val m = readLine().toInt()
    var a = arrayOf<String>()
    repeat(m) {
        val input = readLine()
        if (!s.contains(input)) a += input
    }

    var result = ""
    for (i in s.indices) {
        if (s.size == 1) {
            result = a[0]
            break
        }
        
        if (s[i] == "?") {
            when (i) {
                0 -> result = a.filter { it.endsWith(s[i + 1][0]) }[0]
                s.lastIndex -> result = a.filter { it[0] == s[i - 1][s[i - 1].lastIndex] }[0]
                else -> {
                    val start = s[i - 1][s[i - 1].lastIndex]
                    val end = s[i + 1][0]
                    result = a.filter { it.startsWith(start) && it.endsWith(end) }[0]
                }
            }

            if (result != "") break
        }
    }

    bw.write(result)
    bw.flush()
    bw.close()
}