(BOJ) 1501 영어 읽기

1501 영어 읽기

• 분류 : 자료구조, 문자열, 해시를 사용한 집합과 맵, 파싱

문제

혹시 인터넷을 하다가, 다음과 같은 식의 문장을 본 적이 있는가?

It is itnersetnig taht pepole can raed smoe grabeld wrods.

원래의 문장은 ‘It is interesting that people can read some garbled words’이다.

각각의 단어들은 제일 첫 문자와 제일 끝 문자를 제외하고는 순서가 뒤섞여 있다.

한 대학에서 시행한 연구 조사 결과에 따르면, (영어 단어를 아는 사람의 경우) 첫 문자와 제일 끝 문자가 일치하고,

그 사이의 문자들은 순서가 어떻게 뒤바뀌어 있더라도 읽는 데 지장이 없다고 한다.

그렇다보니, 한 단어가 여러 단어로 해석될 수도 있다.

예를 들어 abcde와 같은 단어는, abcde, abdce, acbde, acdbe, adbce, adcbe 같은 단어들로 해석될 수도 있다.

물론 각각의 단어들이 실제로 존재하는 단어(사전에 존재하는 단어)일 경우에만 의미가 있다.

영어 문장이 주어졌을 때, 그 문장을 해석하는 방법의 경우의 수를 구하는 프로그램을 작성하시오.

각각의 단어는, 첫 글자와 끝 글자가 일치하는 다른 단어(사전에 존재하는)로 해석할 수 있다.

영어 문장은 하나 이상의 단어로 이루어져 있으며, 각 단어들은 공백으로 구분되어 있다.

입력

첫째 줄에 사전에 있는 단어들의 개수 N(0 ≤ N ≤ 10,000)이 주어진다.

다음 N개의 줄에는 각 줄에 하나씩, 영어 사전에 있는 단어들이 주어진다.

각 단어의 길이는 100자를 넘지 않는다.

다음 줄에 해석할 문장의 개수 M(0 ≤ M ≤ 10,000)이 주어진다.

다음 M개의 줄에는 각 줄에 하나씩 문장이 주어진다.

각 문장의 길이는 10,000자를 넘지 않는다. 영어 단어는 알파벳 대소문자(구별됨)로만 이루어진다.

출력

M개의 줄에, 각 문장을 해석하는 경우의 수를 출력한다. 답은 32-bit signed int 범위 안에 있다고 가정하자.

예제 입력 1

3
ababa
aabba
abcaa
2
ababa
abbaa

예제 출력 1

2
2

Solution

Expander

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

private var N: Int = 0
private var dictionary = mutableListOf<String>()
private var M: Int = 0
private var sentence = mutableListOf<String>()

private var numberOfCase = mutableMapOf<String, Int>()

fun main() {
    input()
    solve()
}

private fun input() = with(BufferedReader(InputStreamReader(System.`in`))) {
    N = readLine().toInt() // 사전에 있는 단어들의 개수 N
    repeat(N) {
        dictionary.add(readLine())
    }
    M = readLine().toInt()
    repeat(M) {
        sentence.add(readLine())
    }
}

private fun solve() {
    dictionary.forEach {
        val key = it.key()
        if (numberOfCase.containsKey(key)) {
            numberOfCase[key] = numberOfCase[key]!! + 1
        } else {
            numberOfCase[key] = 1
        }
    }
    sentence.forEach {
        val words = StringTokenizer(it)
        var result = 1

        while(words.hasMoreTokens()) {
            val key = words.nextToken().key()
            var count = 0
            if (numberOfCase.containsKey(key)) {
                count = numberOfCase[key]!!
            }
            result *= count
        }
        println(result)
    }
}

private fun String.key(): String {
    if (this.length < 3) {
        return this
    }
    val prefix = "${this.first()}${this.last()}"
    val body = this.substring(1, this.length - 1).sort()
    return prefix + body
}

private fun String.sort() = String(toCharArray().apply { sort() })

Point of Thinking

• Scanner로 읽은 값이 공백 기준으로 제대로 split이 안되었다.
  • 로직 변경없이 BufferedReader와 StringTokenizer로 교체하였음.
• 처음에 주어지는 문자열들로 사전을 구성할때 자체적인 hash값을 만드는 게 필요하다.
  • 여기서는 문제의 조건대로 첫글자와 끝글자를 제일 앞에 두고, 나머지 문자열을 오름차순으로 정렬하여 unique key로 사용하였다.
  • 동일한 key가 이미 Set에 있을 경우 카운트를 계속 올려준다.
• 주어지는 문장내 단어들의 key를 뽑아 사전에 있는 지 검증해나가면서 최종값에 곱해주면 그게 바로 모든 경우의 수가 되면서 Accepted.