[백준][코틀린][1339] 단어 수학

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

1339번: 단어 수학

문제 풀이

1. 주어진 입력을 중복 없이 알파벳으로 저장한 뒤 0 ~ 9 까지 하나씩 숫자를 넣어서 최대 합을 구하였더니 시간이 너무 오래 걸렸다.

2. 수학적인 접근 법을 이용하여 탐색 시간을 최소한으로 한다.

3. 문자열의 더하기에서 각 문자열은 숫자가 어떤 값인지는 알 수 없는 상황이지만 몇의 자리 수 인지는 파악할 수 있다. 예를 들어 입력이 GCF 일 경우 G 는 100의 자리 수, C 는 10의 자리 수, F 는 1의 자리 수이다. 이를 이용하여 ACDEB 에 대해서도 동일하게 자리를 수를 구하면 A는 10000의 자리 수, C 는 1000의 자리 수, D 는 100의 자리 수, E는 10의 자리 수, E 는 10의 자리 수, B 는 1의 자리 수이다.

4. 3번에서 구한 각 단어를 자리 수 기준으로 더한다.

GCF + ACDEB = 100G + 10C + 1F + 10000A + 1000C + 100D + 10E + 1B = 100G + 1010C + 1F + 10000A + 100D + 10E + 1B

5. 4번의 내용을 자리 수 길이 기준으로 내림 차순 정렬 한다.

10000A + 1010C + 100D + 100G + 10E + 1B + 1F

6. 9부터 차례대로 알파벳에 숫자를 입력한 뒤 결과를 구한다.

코드

import java.io.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val N = br.readLine().toInt()
    val strList = Array(N) { "" }
    repeat(N) {
        strList[it] = br.readLine()
    }

    // 입력된 단어의 알파벳의 자리 수를 구해서 list 에 저장한다.
    val list = ArrayList<Alphabet>()
    strList.forEach { str ->
        var pow = 1

        for (i in str.length - 1 downTo 0 step 1) {
            val s = str[i].toString()
            var contains = false
            var containsIndex = -1

            for ((index, l) in list.withIndex()) {
                if (l.alphabet == s) {
                    contains = true
                    containsIndex = index
                    break
                }
            }

            if (contains) {
                list[containsIndex].pow += pow
            } else {
                list.add(Alphabet(s, pow))
            }

            pow *= 10
        }
    }

    //println("$list")

    // 자리수를 기준으로 내림 차순 정렬 한다.
    list.sortByDescending { it.pow }
    //println("$list")

    // 정렬된 리스트를 기준으로 알파벳에 9부터 큰 숫자를 넣는다.
    var number = 9
    var result = 0

    for (l in list) {
        result += l.pow * number
        number--
    }

    println(result)
}

private data class Alphabet(var alphabet: String, var pow: Int)