[백준] 15829 (Hashing)

#1 알고리즘

#1-1 직관적인 풀이와 그 한계

#3-1에 있는 50점 짜리 코드는 누구나 생각할만한 직관적인 풀이다. 문제는, L이 큰 경우다. L이 큰 경우는 나머지 연산을 연산 중간 중간에 끼워서 수가 너무 커지지 않게 조절해야 한다. 하지만, 예를 들어 L이 30이라면 31³⁰라는 엄청나게 큰 수를 계산해야하는데 이건 말이 안 된다.

 

따라서 이 문제는 #3-1에 있는 직관적인 풀이가 아닌 새로운 방식으로 풀어야 한다는 분위기를 풍긴다. 다행히, 문제의 힌트에서 무언가가 보인다.

 

#1-2 힌트

abcde의 해시 값은 1 × 31⁰ + 2 × 31¹ + 3 × 31² + 4 × 31³ + 5 × 31⁴ = 1 + 62 + 2883 + 119164 + 4617605 = 4739715이다.

반복되는 숫자가 눈에 띈다. 바로 31이다. 대한민국에서 중ㆍ고등학교를 나온 사람이라면 무의식적으로 위 수식을 31 × ( ... )와 같은 형태로 묶고 싶어질 것이다. 나도 그렇다. 한번 묶어 보겠다.

 

#1-3 괄호 정리

1 × 31⁰ + 2 × 31¹ + 3 × 31² + 4 × 31³ + 5 × 31⁴ =
1 + 31 × (2 × 31⁰ + 3 × 31¹ + 4 × 31² + 5 × 31³) =
1 + 31 × (2 + 31 × (3 × 31⁰ + 4 × 31¹ + 5 × 31²)) =
1 + 31 × (2 + 31 × (3 + 31 × (4 × 31⁰ + 5 × 31¹))) =
1 + 31 × (2 + 31 × (3 + 31 × (4 + 31 × (5 × 31⁰))))

이렇게 정리하면, 31³⁰과 같은 무식하게 큰 숫자가 나오지 않게 할 수 있다. 또, 아래에 나눠 놓은 ㄱ ~ ㅁ단계처럼 규칙성 있는 형태를 뽑아낼 수 있다.

 

ㄱ. 31 × (5 + 0)
ㄴ. 31 × (4 + ㄱ)
ㄷ. 31 × (3 + ㄴ)
ㄹ. 31 × (2 + ㄷ)
ㅁ. (1 + ㄹ)

ㄱ단계에서 ㅁ단계까지 가는 규칙성이 눈에 보인다. 이 규칙성을 토대로 코드를 짠다. 각 단계 중간 중간마다 나머지 연산을 잊지 말자.

 

#2 여담

힌트가 없었으면 꽤 고전했을 것이다. (힌트가 없었다면) 엄청나게 어렵진 않았겠지만, 그렇다고 엄청 쉽지도 않았을 것이다.

 

#3 코드 - 코틀린

#3-1 50점짜리 코드

import kotlin.math.pow

const val r: Double = 31.0
const val m = 1234567891

fun main() {
    // 입력 받기
    val l = readln().toInt()
    val inputtedAlphabets = readln()

    // 계산
    var sum = 0.0
    for (i: Int in 0..<l) {
        val a = inputtedAlphabets[i].code - 96
        val powOfR = r.pow(i.toDouble())

        sum += a * powOfR
    }

    // 출력
    println((sum % m).toInt())
}

#1-1에서 말한 '직관적인' 코드다. 실제로 백준 사이트에서 50점이라고 출력된다.

 

#3-2 100점짜리 코드

const val m = 1234567891

fun main() {
    // 입력 받기
    val l = readln().toInt()
    val inputtedAlphabets = readln()

    // 계산
    var sum: Long = 0
    for (i: Int in (l - 1) downTo 0) {
        val a = inputtedAlphabets[i].code - 96
        sum = if (i == 0) {
            sum + a
        } else {
            31 * (sum + a)
        }

        sum %= m
    }

    // 출력
    println(sum)
}

sum을 Long이 아닌 Int로 두면, 일정 수 이상의 큰 수부터는 2.4811904E7와 같은 표기법으로 표시해버린다. 따라서 알고리즘이 위 코드와 동일해도 sum의 데이터형이 Int라면 50점이 나온다.