[BOJ/Silver 5] 백준 28432 끝말잇기(Kotlin)

문제 링크

https://www.acmicpc.net/problem/28432

28432번: 끝말잇기

 

문제

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

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

 

입력

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

다음 줄에 후보 단어의 개수 M이 주어집니다. (1 ≤ M ≤ 100)다음 M개의 줄에는 후보 단어 A1, ⋯, AM이 주어집니다. Ai는 길이 2이상 10이하의 영어 소문자로 이루어진 문자열입니다. A1, ⋯, AM은 서로 다릅니다.

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

 

출력

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

 

예제 입력 1

5
charlie
echo
?
romeo
oscar
3
alfa
oscar
or

예제 출력 1

or

 

 

알고리즘 분류

• 문자열

 

풀이

먼저 N개의 문자열을 입력받으며 전부 배열에 추가하고 ?이 등장한다면 ? 바로 앞에 등장한 문자열의 마지막 문자 A와 ? 바로 뒤에 등장할 문자열의 첫 번째 문자 B를 기록한다.

이후 M개의 문자열을 입력받으며 배열에 존재하지 않는 문자열들의 첫 번째 문자와 마지막 문자를 탐색하여 이미 기록한 A, B와 일치하는지를 판단한다. A가 없다면 첫 번째 문자는 어떤 문자여도 상관없고, B가 없다면 마지막 문자는 어떤 문자여도 상관없다.

문제에 대한 답은 반드시 하나만 존재하므로 답을 찾았다고 해서 입력을 멈출 필요는 없다.

 

코드

import java.util.*

var arr: Array<String> = arrayOf()

fun main() = with(Scanner(System.`in`)) {
    var answer = ""
    val n = nextLine().toInt()
    var a = ""
    var b = ""
    for (i in 0 until n) {
        val s = nextLine()
        if (s == "?") {
            if (i > 0) {
                a = arr[i - 1].last().toString()
            }
        }
        else if ((i > 0) && (arr[i - 1] == "?")) {
            b = s.first().toString()
        }
        arr = arr.plus(s)
    }
    val m = nextLine().toInt()
    for (i in 0 until m) {
        val s = nextLine()
        if (arr.contains(s)) {
            continue
        }
        if ((a != "") && (s.first().toString() == a)) {
            if ((b != "") && (s.last().toString() == b)) {
                answer = s
            }
            else if (b == "") {
                answer = s
            }
        }
        else if (a == "") {
            if ((b != "") && (s.last().toString() == b)) {
                answer = s
            }
            else if (b == "") {
                answer = s
            }
        }
    }

    println(answer)
}