백준 1339 단어 수학

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

알파벳으로 이루어진 단어들이 주어지고, 각 알파벳을 중복되지 않도록 임의의 숫자로 치환하여 만든 숫자들의 합들 중 최댓값을 구하는 문제이다.

최대 10종류의 알파벳이 있으며 10개의 단어가 주어지고, 각 단어의 길이는 최대 8이다.

단순히 앞의 알파벳에서 시작해서 9부터 준다면 문제가 발생한다.

ABCDE
BGDF
GABC
GEDC

위와 같은 케이스에서, A에게 9를 주고 다음 천의 자리인 B 또는 G에 8을 줘야 한다.

여기서 B에 8을 넣을지 G에 8을 넣을지는 이후 백의 자리부터 일의 자리까지 매 자리마다 B와 G의 개수를 비교해서 숫자를 넣어야 한다.

B에 8을 넣어버리면 다음 백의 자리에서 B가 없고 G만 있으므로 최댓값을 보장할 수 없어진다.

또한 B와 G 뿐만아니라 같은 개수의 알파벳이 여러 개일 경우를 생각하면 복잡해진다.

그래서 앞에서부터 숫자를 대입하는 방법은 무리일 것 같고 자릿수에 초점을 두었다.

A가 만의 자리이므로 값을 10,000
B는 천의 자리 2개에 십의 자리 1개가 있으므로 값을 2010
C는 백의 자리 1개에 일의 자리 2개가 있으므로 값을 102
D는 십의 자리 3개이므로 값을 30
E는 백의 자리 1개에 일의 자리 1개이므로 101
F는 일의 자리 1개이므로 1
G는 천의 자리 2개에 백의 자리 1개이므로 2100

각 자릿수의 값을 구한 다음 값이 큰 순서대로 9부터 넣어주면 된다.

A - 9, G - 8, B - 7, C - 6, E - 5, D - 4, F - 3

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()

    val words = Array(N){readLine()}.sortedWith{w1, w2 -> w2.length - w1.length}

    val maxLen = words[0].length

    val cArr = Array(N){CharArray(maxLen){' '}}
    val cMap = mutableMapOf<Char, Int>()

    for(i in words.indices){
        for(j in maxLen - words[i].length until maxLen){
            cArr[i][j] = words[i][j - (maxLen - words[i].length)]
        }
    }

    var mul = 1
    for(j in maxLen - 1 downTo 0){
        for(i in cArr.indices){
            if(cArr[i][j] == ' ') continue
            if(cMap[cArr[i][j]] == null) cMap[cArr[i][j]] = 0
            cMap[cArr[i][j]] = cMap[cArr[i][j]]!! + mul
        }
        mul *= 10
    }

    val sorted = cMap.entries.sortedWith{e1, e2 -> e2.value - e1.value}

    var nextNum = 9

    val transMap = mutableMapOf<Char, Int>()

    sorted.forEach { entry ->
        transMap[entry.key] = nextNum--
    }

    var sum = 0
    val wordsArr = words.map{it.toCharArray()}
    for(i in wordsArr.indices){
        for(j in wordsArr[i].indices){
            wordsArr[i][j] = transMap[wordsArr[i][j]]!!.digitToChar()
        }
        sum += String(wordsArr[i]).toInt()
    }

    print(sum)
}

편의를 위해 문자열을 같은 길이의 CharArray로 일의 자리부터 맞추었다.

GCF
ACDEB

라면

A C D E B
'.' '.' G C F

이런 식으로 변경한 후, 일의 자리부터 mul을 더하고 *=10을 해주며 각 알파벳들에 해당하는 값을 구하였다.

이후 value 값을 기준으로 정렬하여 Char - Int로 매핑하는 transMap을 만들고, 문자열의 각 값을 숫자로 바꾼 값을 더하며 sum을 구했다.