백준 1132번 합 코틀린 kotlin - 난이도 골드3
문제
주어진 입력 값인 알파벳에 숫자를 대입하여 변환한 후 합의 최대값을 구하는 문제이다.
접근
- 방정식 및 자릿수를 활용하여 변환하여 풀어야 함. 경우의 수를 DFS/BFS로 구하면 시간 초과 남(처음에 아무생각 없이 해봤으나 시간초과)
- 0~9까지의 숫자를 사용할 수 있으나 제일 앞자리 오는 알파벳들은 0으로 사용불가 하므로 적절하게 교체해줘야 함
- ABC = 100A + 10B + 1*C 와 같음
- ABC + BCA = 100A+10B+C + 100B+10C+A = 110B + 101A + 11C 이므로 앞에서부터 9 8 7 을 대입하여 계산하면 됨
풀이
1번
fun main() {
var answer = 0L
val sc = Scanner(System.`in`)
val n = sc.nextInt()
var arr = LongArray(10)
var isFirstZeo = BooleanArray(10) { false }
for (i in 1..n) { //n은 50보다 작거나 같은 자연수
val b = sc.next()
calc(arr, b)
isFirstZeo[check(b[0])] = true
}
// (index, LongValue) 로 맵핑 후 LongValue가 0이 아닌 값들 중 내림차순으로 정렬
var list: MutableList<Value> = mutableListOf()
arr.mapIndexed { index, l -> list.add(Value(index, l))}
list = list.filter { it.value != 0L }.sortedByDescending { it.value }.toMutableList()
//마지막에 위취한 값의 알파벳이 0이 되면 안되므로 0키 되도 되는값을 찾은 후 한칸씩 밀어주기
if (list.size == 10 && isFirstZeo[list[9].idx]) {
for (i in 8 downTo 0) {
if (!isFirstZeo[list[i].idx]) {
val item = list[i]
list.removeAt(i)
list.add(item)
break
}
}
}
var num = 9L
for (item in list) {
answer += num-- * item.value
}
println(answer)
}
private fun calc(arr: LongArray, str: String) {
val size = str.length
for (i in 0 until size) {
val mul = Math.pow(10.0, (size - i - 1).toDouble()).toLong()
val idx = check(str[i])
arr[idx] = arr[idx] + mul
}
}
private fun check(ch: Char): Int {
var res = -1
when (ch) {
'A' -> res = 0
'B' -> res = 1
'C' -> res = 2
'D' -> res = 3
'E' -> res = 4
'F' -> res = 5
'G' -> res = 6
'H' -> res = 7
'I' -> res = 8
'J' -> res = 9
}
return res
}
data class Value(val idx: Int, val value: Long)
- 1단계 : 주어진 값이 정수의 범위를 넘어설 수 있다는 것을 인지해야 함
- 2단계 : 입력값을 받으면서 제일 앞자리의 알파벳의 숫자가 0 유무 체크
- 3단계 : 리스트에 문자열을 다 넣고 변환 된 값(ex 110B 101A 99C)의 계 내림차순으로 정렬
- 4단계 : 10자리인 경우 0을 반드시 사용하므로 제일 마지막에 위치한 문자부터 0을 써도 되는지 체크하면서 불가능하면 앞으로 이동하면서 0을 써도 되는 문자을 찾은 후 한칸씩 밀기
- 5단계 : 문자 탐색하면서 계산
이 문제는 예외처리를 잘 따져가면서 구현을 하는 문제이다. 조심해야할 점은 결과가 Int범위 초과한다는 점과 제일 앞자리에는 0이 오지 못한다는 점이다
결론
- 코틀린 filter map 이거 너무 좋음