개발해요

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

프로세스

1. 모든 단어는 'a', 'n', 't', 'i', 'c', 다섯 글자를 포함한다.
2. 21개의 글자 중 k-5개를 뽑는 조합을 구한다. (위 다섯 글자는 미리 포함시킨다)
3. 조합마다 읽을 수 있는 단어 수를 구해서 정답과 비교한다. (앞 뒤 공통 글자들은 제외하고 확인)

풀이

알파벳 소문자로 구성된 n개의 단어 중에서, k개의 알파벳만 가지고 만들 수 있는 단어의 최대 개수를 구하는 문제이다.

(1<=n <=50, 0<=k<=26, 8<=단어 길이<=15)

완전 탐색)

여러 풀이 방법이 있는 것 같은데, 나는 모든 k개의 경우의 수를 살펴보는 완전 탐색 방법을 사용했다.

완전 탐색의 연산 횟수를 계산해보자. (1) 26개의 알파벳 중 k개의 경우의 수를 구해서 (2) 각 케이스마다 몇 개의 단어를 만들 수 있는지 확인해야는데, (3) 각 단어마다 어떤 알파벳들로 구성되어 있는지 확인해야 한다. 이를 계산해보면, 최대 연산 횟수는 (26C13) *  50 * 15 = 78억 번으로 1초 만에 통과할 수 없다.

그럼 어떻게 해야 할까?

문제의 조건에 따르면 남극의 모든 단어는 "anta"로 시작해서 "tica"로 끝나므로, 단어를 구성하기 위해선 'a', 'c', 'n', 't', 'i' 5글자는 반드시 포함해야 한다. 그럼 21개의 알파벳 중에서 k-5개의 경우의 수만 구하면 되므로, (21C10) * (15-8)(앞 뒤 네 글자 제외) * 50(단어 수) = 약 1.2억 번의 연산 횟수가 나온다. 나는 1초를 1억 번 정도의 연산으로 알고 있었는데, 요즘 컴퓨터는 1초에 10억 번은 거뜬히 계산한다고 한다. 그러니까 2억 6천 번 정도면 통과 가능한 수치라고 생각할 수 있다! 

이제 지금까지의 과정에 따라 그대로 구현하면 정답을 찾을 수 있다. 나는 조합 함수를 재귀로 구현해서, k-5개의 알파벳 조합을 찾을 때마다 모든 단어를 확인했다. 그리고 그 조합으로 만들 수 있는 단어의 개수를 찾아서 기존의 최대 값과 비교하는 방식으로 구현했다. 

또, n개의 단어를 Set으로 저장해서, 조합을 찾고 단어와 비교할 때 좀 더 빠르게 연산할 수 있도록 했다. 

코드1

import kotlin.math.max

var answer = 0
var n = 0
var k = 0
val alphabets = ('a'.code..'z'.code).filter{ it.toChar() !in "antic" }	// 5개 제외한 알파벳

fun main() {
    readLine()!!.split(" ").let{
        n = it[0].toInt()
        k = it[1].toInt()
    }
    // 5개 미만의 글자로는 어떤 단어로 읽을 수 없다. 
    if (k < 5){
        println(0)
        return
    }

    val words = Array(n){setOf<Char>()}	 // 각 단어의 알파벳 set을 담는 배열
    for (i in 0 until n){
        words[i] = readLine()!!.toSet()
    }

    combine(words, 0, 0, "antic".toMutableList())  // 조합을 찾을 때마다 만들 수 있는 단어 개수 확인
    println(answer)
}

fun combine(words: Array<Set<Char>>, startIdx: Int, combinationCount: Int, combination: MutableList<Char>){
    if (k-5 == combinationCount){	// a,n,t,i,c를 제외하고 k-5개의 글자 조합을 찾으면
        var count = 0
        words.forEach { word ->			// 현재 조합으로 단어를 만들 수 있는지 확인
            if (combination.containsAll(word)){	// '=='으로 확인하면 조합의 글자 수가 더 많은 경우를 놓친다.
                count += 1
            }
        }
        answer = max(answer, count)
        return
    }

    for (i in startIdx until 21){
        combination.add(alphabets[i].toChar())
        combine(words, i+1, combinationCount+1, combination)
        combination.removeAt(5+combinationCount) // 조합에 기본적으로 5개 글자가 들어있음
    }
}

코드2

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.max

val srcLetters = mutableListOf<Char>()
var numOfPick = 0
lateinit var pickedLetters: MutableSet<Char>
lateinit var setsOfWords: Array<MutableSet<Char>>
var answer = 0

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (numOfWords, numOfLetters) = readLine().split(" ").map(String::toInt)

    if (numOfLetters == 26) {
        println(numOfWords)
        return
    } else if (numOfLetters < 5) {
        println(0)
        return
    }

    val fixedLetters = arrayOf('a', 'n', 't', 'i', 'c')
    numOfPick = numOfLetters - 5
    setsOfWords = Array(numOfWords){ HashSet() }
    pickedLetters = HashSet()

    repeat(numOfWords) { setIndex ->
        val word = readLine()
        for (i in 4 until word.length - 4) {
            if (word[i] !in fixedLetters) {
                setsOfWords[setIndex].add(word[i])
            }
        }
    }

    for (ch in 'b'..'z') {
        if (ch !in fixedLetters) {
            srcLetters.add(ch)
        }
    }

    pick(0, 0)

    println(answer)
}

fun pick(count: Int, startIndex: Int) {
    if (count >= numOfPick) {
        val readCount = getHowManyRead()
        answer = max(answer, readCount)
        return
    }

    // 앞으로 뽑아야 할 문자 수 > 남아있는 문자 수
    if (numOfPick - count > 21 - startIndex) {
        return
    }

    for (i in startIndex until 21) {
        pickedLetters.add(srcLetters[i])
        pick(count + 1, i + 1)
        pickedLetters.remove(srcLetters[i])
    }
}

fun getHowManyRead(): Int {
    var count = 0

    for (word in setsOfWords) {
        if (isReadable(word)) count++
    }

    return count
}

fun isReadable(word: Set<Char>): Boolean {
    for (ch in word) {
        if (ch !in pickedLetters) return false
    }

    return true
}

리뷰

• 시간 복잡도 계산하는 게 좀 거부감이 느껴진다. 그렇게 무시하고 풀다가 결국 시간 초과라는 걸 마주하게 된다. 익숙해져야지.
• 무시할 수 있는 문제 조건 같은 건 없다. 예를 들면 antic이라던지, antic이라던지..ㅠㅠ