[백준] 단어 수학 (1339)(kotlin)

문제 설명

백준 1339번 문제 링크

입력 및 출력

» 입력

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

» 출력

첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

예제 입출력(테스트케이스)

입력	출력
2 AAA AAA	1998
2 GCF ACDEB	99437
10 A B C D E F G H I J	45
2 AB BA	187

문제 풀이1

• 가정

  • 알파벳의 출현 갯수(weight)와 상관 없이, 자릿수가 가장 높은 알파벳이 우선적으로 가장 큰 수가 되어야함
  • 자릿수(idx)가 같은 알파벳 발생시, 알파벳의 출현 갯수(weight)가 가장 많은 것이 사용할 수 있는 수들 중 가장 큰 수가 되어야 함

import kotlin.math.pow

// 알파벳의 각 가중치를 저장할 Class를 생성
// char -> 알파벳 자신(의 인덱스)
// weight -> 알파벳의 출현 빈도수
// idx -> 자리수의 합
class NUM(var char: Int, var weight: Int, var idx: Int) : Comparable<NUM> {
    override fun compareTo(other: NUM): Int {
        return if (this.idx == other.idx) {
            this.weight - other.weight
        } else {
            this.idx - other.idx
        }
    }
}

fun main() = with(System.`in`.bufferedReader()) {
    // 'A' ~ 'Z'까지 알파벳의 각 가중치를 저장할 배열을 생성 및 초기화
    val aArr = Array(26) { NUM(it, 0, 0) }
    val n = readLine().toInt()
    // 더해야할 알파벳들을 배열에 생성과 동시에 저장
    var numbers = Array<String>(n) { readLine() }

    // numbers 배열의 알파벳들을 하나씩 전부 탐색
    numbers.forEach { str ->
        str.forEachIndexed { index, num ->
            // 알파벳의 빈도수 증가
            aArr[num - 'A'].weight++
            // 알파벳의 자리수를 더함
            aArr[num - 'A'].idx += 10.0.pow(str.length - index).toInt()
        }
    }

    // 위 2중 foreach에서 추출한 글자들에 대한 정보를 바탕으로
    // NUM클래스의 compareTo메소드를 활용하여 내림차순으로 정렬
    // 정렬 후, 가장 큰 수가 되어야할 것이 0번 인덱스부터 차례대로 정렬됨
    aArr.sortDescending()

    // 더해야할 알파벳들에서 사용된 알파벳이 총 몇개인지 카운트
    var ints = aArr.count { it.weight != 0 }
    // 알파벳을 숫자로 변환할 map 선언
    val intMap = mutableMapOf<Char, Int>()

    // 내림차순으로 정렬된 aArr의 0번 인덱스부터,
    // 사용된 알파벳의 총 갯수까지 숫자로 변환
    for (i in 0 until ints) {
        intMap['A' + aArr[i].char] = 9 - i
    }

    // 결과를 저장할 변수 선언
    var answer = 0
    // 입력 받은 알파벳 한 줄 통째로 숫자로 변환하는 작업을 수행
    for (number in numbers) {
        var str = ""
        for (char in number) {
            // 입력 받은 알파벳에서 하나의 알파벳을 꺼내서 숫자로 변환하여 str에 append
            str += intMap[char]!!
        }
        // 전부 숫자로 변환된 한 알파벳 라인을 int로 변환하여 answer에 더함
        answer += str.toInt()
    }

    // 다 더해진 숫자들을 출력
    println(answer)
}