1148번: 단어 만들기

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

 

언어 : Kotlin

 

문제 설명 :

어떤 신문엔 이러한 퍼즐이 있다. 3x3의 표에 영문자가 하나씩 있으며, 이 영문자들을 사용해서 최대한 많은 영단어를 만드는 것이 목표이다. 예를 들면, 아래의 퍼즐판에서는 'LINT', 'TILL', 'BRILLIANT' 등을 만들 수 있다.

단어는 최소 4글자 이상이어야 하며, 한 글자당 최대 1번만 사용할 수 있다. 따라서 10글자 이상의 단어는 만들 수 없다. 또한, 표의 정중앙에 있는 글자는 반드시 사용해야 한다. 위 퍼즐판의 경우 'I'는 반드시 사용해야 한다.

따라서 어떤 글자가 가운데에 있느냐에 따라 퍼즐의 난이도는 천차만별일 것이다. 퍼즐 제작자 남규는 퍼즐판에 어떤 글자를 배치할지는 결정했으나 멍청해서 어떤 글자를 가운데에 놓을지까지는 정하지 못했다.

보다 못한 조수 재혁이가 어떤 글자를 놓아야 퍼즐이 가장 쉬워지는지(즉, 만들 수 있는 단어의 개수가 가장 많음), 또 어떤 글자를 놓아야 퍼즐이 가장 어려워지는지(즉, 만들 수 있는 단어의 개수가 가장 적음)를 알려주려고 한다. 그러나 재혁이가 망각한 사실이 있으니 자신도 멍청하다는 것이었다. 따라서 당신이 이 문제를 대신 풀어주어야 한다.

또한 문제 속 세상의 사람들은 우리보다도 멍청해서, 우리보다 훨씬 적은 수의 영단어를 사용한다. 이 단어들을 모두 담고 있는 사전과 퍼즐판에 배치할 9개의 문자가 주어졌을 때, 문제를 푸는 프로그램을 작성하시오.

 

입력 :

입력의 처음에는 사전을 이루는 최대 20만 개의 단어가 주어진다. 각 단어는 4~9글자의 영어 대문자로 이루어져 있으며, 한 줄에 하나씩 주어진다. 또한 사전순으로 정렬되어 있다. 사전 입력의 끝에는 한 줄에 걸쳐 '-' 한 글자가 주어진다.

그 다음부터 여러 개의 퍼즐판이 주어진다. 각 퍼즐판은 9개의 영어 대문자로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 맨 끝에는 한 줄에 걸쳐 '#' 한 글자가 주어진다.

 

출력 :

각 퍼즐판마다 정답을 예제 형식에 맞게 한 줄에 하나씩 출력한다.

각 문제마다 정답의 개수를 가장 적게 하기 위해 정중앙에 놓아야 할 문자들과 그때의 정답 개수, 정답의 개수를 가장 많게 하기 위해 정중앙에 놓아야 할 문자들과 그 때의 정답 개수를 공백으로 구분하여 출력한다.

한 개 이상의 문자가 답을 만족할 경우 문자들을 알파벳순으로 정렬하여 출력하며, 중복된 문자는 출력하지 않는다. 첫 번째 예제 출력에서 보듯이 I나 L은 여러 번 등장하지만 한 번씩만 출력하였다.

 

제한 사항 :

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

 

입출력 예 :

입력	출력
APPLE BANANA BANE BRILLIANT LINT PALE PROBLEM TILL TRILL - LARBITNLI LEPAPBNNA LEPAPBNAM #	AB 1 ILT 4 BN 1 AE 3 M 0 AE 3

 

풀이 : 

저장한 단어들의 문자와 퍼즐의 문자를 각각 비교하여, 해당 단어의 문자 수가 퍼즐에 부합하지 않다면(문자가 더 많다거나 특정 문자가 없다거나) 무시하고 부합할 경우에만 result에 카운팅을 한다.

 

이를 input 받은 단어 전체에 시행하고 result 값의최소 최대를 확인하고 출력한다.

import java.io.BufferedWriter
import java.io.OutputStreamWriter

const val MAX_WORD = 200000

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

    val words = ArrayList<IntArray>(MAX_WORD)

    while (true) {
        val word = readLine()
        if (word == "-") break

        val wordCnt = IntArray(26)
        for (c in word) wordCnt[c - 'A']++

        words.add(wordCnt)
    }

    val output = StringBuilder()
    while (true) {
        val puzzle = readLine()
        if (puzzle == "#") break

        val puzzles = IntArray(26)
        for (c in puzzle) puzzles[c - 'A']++

        val result = IntArray(26)
        var min = MAX_WORD + 1
        var max = 0

        for (word in words) {
            var isValid = true

            for (i in 0 until 26) {
                if (word[i] > puzzles[i]) {
                    isValid = false
                    break
                }
            }

            if (isValid) {
                for (i in 0 until 26) {
                    if (word[i] > 0) result[i]++
                }
            }
        }

        for (i in 0 until 26) {
            if (puzzles[i] > 0) {
                if (min > result[i]) min = result[i]
                if (max < result[i]) max = result[i]
            }
        }

        for (i in 0 until 26) {
            if (puzzles[i] > 0 && result[i] == min) {
                output.append('A' + i)
            }
        }
        output.append(" $min ")

        for (i in 0 until 26) {
            if (puzzles[i] > 0 && result[i] == max) {
                output.append('A' + i)
            }
        }
        output.append(" $max\n")
    }

    bw.write(output.toString())
    bw.flush()
    bw.close()
}