1036번: 36진수

문제 출처 : https://www.acmicpc.net/problem/1036

 

언어 : Kotlin

 

문제 설명 :

36진법의 숫자는 0부터 9까지의 수와 알파벳 A에서 Z로 나타낸다. A부터 Z까지 알파벳은 10부터 35에 차례대로 대응한다.

36진법의 수 N개가 주어진다. 36진법 숫자(0-9, A-Z) 중에서 K개의 숫자를 고른다. 그러고 나서 N개의 수 모두에서 나타난 그 숫자를 Z로 바꾼다. 그 이후에 N개의 수를 모두 더한다.

이때 가능한 합의 최댓값을 구하는 프로그램을 작성하시오. 합의 최댓값도 36진수로 출력한다.

 

입력 :

첫째 줄에 수의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 수가 주어진다. N은 최대 50이고, 수의 길이도 최대 50이다. 마지막 줄에 K가 주어진다. K는 36보다 작거나 같은 자연수 또는 0이다.

 

출력 :

첫째 줄에 문제의 정답을 출력한다.

 

제한 사항 :

• 시간 제한 : 2초
• 메모리 제한 : 128MB

 

입출력 예 :

입력	출력
5 GOOD LUCK AND HAVE FUN 7	31YUB
1 HELLO 2	ZZLLO
5 500 POINTS FOR THIS PROBLEM 5	1100TC85
6 TO BE OR NOT TO BE 0	QNO
1 KEQUALS36 36	ZZZZZZZZZ

 

풀이 : 

문제가 어려워서 다른 사람의 풀이를 참고했다.

https://jimoo-vision.tistory.com/30

백준 1036 36진수 java 자바 - jimoo

 

주어진 문자열의 각 문자를 Z로 바꿨을 때 총 합에 큰 영향을 끼치는 문자 K개를 Z로 바꾼 뒤 모두 합쳐 36진수로 바꾸는 문제이다.

 

예제 2의 HELLO를 예로 들어보자.

36진법은 0 ~ 9, 10부터는 A ~ Z 문자로 나타낸다.

즉, Z = 35이다.

NUM	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E
NUM	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29
	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T
NUM	30	31	32	33	34	35
	U	V	W	X	Y	Z

 

이것을 자릿수에 맞추고 셈을 해주자.

	총 합에 영향을 끼치는 크기	전부 Z 변경 영향력 계산	일부 Z 변경  합산
H	35 * 36 ^ 4 - 17 * 36 ^ 4	30,233,088	58,786,560
E	35 * 36 ^ 3 - 14 * 36 ^ 3	979,776	1,632,960
L	35 * 36 ^ 2 - 21 * 36 ^ 2	18,144	27,216
L	35 * 36 ^ 1 - 21 * 36 ^ 1	504	756
O	35 * 36 ^ 0 - 24 * 36 ^ 0	11	24
SUM	K = 2 이므로, 가장 큰 영향은 [H, E]		60,447,516

 

위 표에서 굵은 표시를 해준 부분이 일부 Z 변경 합산에 들어간 값이다.

SUM = 60,447,516(10진법)을 36진법으로 바꿔주면 ZZLLO가 나온다.

 

 

1. 입력 받은 36진법의 수를 반복문을 돌려 각 문자가 Z로 바꿨을 때의 영향력을 확인할 check()
2. 총합을 10진수로 더하는 함수 sum()
3. 마지막으로 10진수를 36진수로 변환하는 함수 change36()

3가지 함수를 만들면 된다.

N의 최대가 50, 길이도 최대 50이므로 매우 큰 값이 들어올 수 있기 때문에 BigInteger를 사용한다.

 

dic이라는 맵을 만들어 1번에서 계산한 문자들을 전부 넣는다. (Set을 쓰지 않는 이유는 같은 문자가 나오더라도 자릿수가 달라서 값은 추가해야할 수 있기 때문 + N이 1이면 상관없지만 N이 2 이상이라면 복수 문자가 나올 수 있기 때문)

 

이후 dic의 값(영향력)을 내림차순으로 정렬하여 K개의 Key값. 즉, 가장 영향력 끼치는 문자를 K개 뽑아낸다.

총합을 10진수로 더하는 것은 arr를 순회하며 영향력 문자에 포함되면 Z로 계산하면 된다.

 

10 진수를 36 진수로 변환하는 것은 진법 변환 알고리즘을 사용한다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.math.BigInteger

lateinit var max: BigInteger
lateinit var arr: Array<String>
val dchar = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
var str = ""
val dic = mutableMapOf<Char, BigInteger>()
val thirtysix = BigInteger("36")

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val n = readLine().toInt()
    arr = Array(n) { readLine() }

    val k = readLine().toInt()
    if (k > 0) {
        check(arr)
        val list = dic.entries.sortedByDescending { it.value }
        str = list.take(k).joinToString("") { it.key.toString() }
    }
    max = sum(arr)
    val answer = change36(max)
    println(answer.reversed())

    bw.flush()
    bw.close()
}

fun check(arr: Array<String>) {
    for (n in arr.indices) {
        for (j in arr[n].indices) {
            val pow = thirtysix.pow(arr[n].length - j - 1)
            var bnum = BigInteger.valueOf(35).multiply(pow)
            val original = pow.multiply(BigInteger.valueOf(dchar.indexOf(arr[n][j]).toLong()))
            bnum = bnum.subtract(original)
            val c = arr[n][j]
            dic[c] = dic.getOrDefault(c, BigInteger.ZERO).add(bnum)
        }
    }
}

fun sum(arr: Array<String>): BigInteger {
    var result = BigInteger.ZERO
    for (i in arr.indices) {
        for (j in arr[i].indices) {
            val c = arr[i][j].toString()
            val pow = thirtysix.pow(arr[i].length - j - 1)
            val num = if (str.contains(c)) {
                pow.multiply(BigInteger.valueOf(35))
            } else {
                pow.multiply(BigInteger.valueOf(dchar.indexOf(c).toLong()))
            }
            result = result.add(num)
        }
    }
    return result
}

fun change36(num: BigInteger): String {
    var localNum = num
    var result = ""
    if (localNum == BigInteger.ZERO) {
        result += "0"
    } else {
        while (localNum > BigInteger.ZERO) {
            result += dchar[localNum.remainder(thirtysix).toInt()]
            localNum = localNum.divide(thirtysix)
        }
    }
    return result
}