[알고리즘] 단어 수학 (백준 1339번)

1339번: 단어 수학

 나올 수 있는 알파벳 종류가 10가지이므로 백트랙킹으로 모든 순열을 구해도 된다. 순열을 구할 때 허용되는 최대 시간복잡도가 10!인데 알파벳이 딱 10가지이기 때문이다.

 하지만 수학 수식을 활용해서 그리디 하게 풀면 훨씬 쉽게 풀 수 있다.

 

Solution

 'ABC', 'BCD' 라는 문자가 있다고 가정해보겠다. 이 두가지 문자를 수학 수식으로 나타내면

• 'ABC' : 100A + 10B + 1C
• 'BCD' : 100B + 10C + 1D

로 표현된다. 그럼 두 수의 합은 100A + 110B + 11C + 1D 로 표현되고 이 수식의 가장 큰 값을 구하기 위해선 곱해지는 상수가 가장 큰 항부터 큰 수를 할당하면 가장 큰 값이 나온다.

 즉 110B, 100A, 11C, 1D 순으로 정렬을하고 B부터 가장 큰 수를 할당해가면 가장 큰 값을 구할 수 있다.

 110 * 9 + 100 * 8 + 11 * 7 + 1 * 6 이 가장 큰 수가 된다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
import kotlin.collections.HashMap
import kotlin.math.max

var br = BufferedReader(InputStreamReader(System.`in`))
var bw = BufferedWriter(OutputStreamWriter(System.out))

fun solution() {

    var N = br.readLine().toInt()

    var max_length = 0

    var words = Array(N, {
        var str = br.readLine()
        max_length = max(max_length, str.length)
        StringBuilder(str)
    })

    var num_list = IntArray(26)

    for(i in 0 until N)
    {
        var ten = 1

        for(j in words[i].length - 1 downTo 0)
        {
            num_list[words[i][j] - 'A'] += ten
            ten *= 10
        }
    }

    //내림차순 정렬
    num_list.sortDescending()

    var result = 0

    //정렬된 수들에 9부터 할당해서 곱하기
    var i = 9

    num_list.forEach {
        result += i * it
        i--
    }

    bw.write(result.toString())

}

fun main() {
    solution()


    br.close()
    bw.close()
}