백준 1394번: 암호

문제: https://www.acmicpc.net/problem/1394

문제 풀이

수학

rank = 해당 문자가 몇을 나타내는지

answer = 암호를 10진수로 변환하면 몇이 되는지 900,528로 나눈 값

mod = 값을 구하기 위해 나누어야 하는 값 = 900,528

메모한 문자 집합의 문자의 개수를 S라고 하면 암호를 S진수로 나타내면 10진수로 몇이 나오는지 구하면 됨

따라서 메모한 문자가 S진수로 몇을 나타내는지 rank[s[i].code] = i + 1로 저장함

암호의 모든 문자 c에 대해서 해당 S진수를 10진수로 나타내는 값 answer * s.length + rank[c.code] % mod를 구해서 answer에 저장함

answer에 암호가 S진수에서 몇 번째 수인지 나타내는 값을 900,528로 나눈 값이 저장되어 있으므로 출력하면 정답

풀이 설명

유진이는 현수의 암호를 알아내려고 한다. 유진이는 사전 조사를 통해 임현수의 컴퓨터에 어떤 문자들이 쓰이는지 알아내었고, 하나씩 대입해보려고 한다. 대입하는 순서는 유진이가 메모한 문자 집합의 순서대로이고, 한 글자부터 암호가 풀릴 때까지 모두 대입해본다.

예를 들어, 메모한 문자 집합이 bca라고 한다면, 유진이는 b, c, a, bb, bc, ba, cb, cc, ca, ab, ac, aa, bbb, bbc, ........ 순서로 암호가 풀릴 때까지 계속 대입해본다.

암호가 풀릴 때까지 대입하는 과정을 살펴보면 메모한 문자 집합의 문자를 사용해 사전 순서로 대입해보는 과정이다. 즉, 이를 다시 생각해보면 메모한 문자 집합의 문자의 수를 S라고 하면 해당 문자들을 숫자로 사용하는 S진수가 몇 번째 숫자인지를 확인하는 것과 같게 된다.

즉, 암호가 S진수로 나타나있을 때 10진수로 변환하면 몇이 되는지 출력하면 된다. 그러므로 암호의 문자를 앞에서부터 $i_1$부터 $i_n$까지라고 하면 10진수로 변환하려면 다음과 같은 식을 통해 바꿀 수 있다.

$i_1 \times S^{n - 1} + i_2 \times S^{n - 2} + \dots + i_n \times S^{0}$

이 식을 사용하기 위해 메모한 문자의 순서에 따라 해당 문자가 숫자 몇에 해당하는지 저장해야 하므로 아스키코드를 이용해 배열에 저장한다. 이에 따라 rank 배열을 정의하고 해당 문자가 몇을 뜻하는지 저장한다.

그 이후에 식을 계산하기 위해 매번 S의 거듭 제곱을 구하는 것은 비효율적이므로 더 빠르게 구할 방법을 찾아야 한다. 식을 살펴보면 더하는 항이 뒤로 갈 수록 S의 거듭 제곱이 1씩 줄어들기 때문에 끝의 항을 제외하면 앞의 항들의 합을 S로 묶을 수 있다는 것을 알 수 있다.

그리고 앞에서 S로 묶었던 항들의 합에서도 동일하게 마지막 항을 제외하면 앞의 항들의 합을 다시 S로 묶을 수 있다는 것을 알 수 있다. 여기서 암호의 앞자리부터 확인할 때 현재 자리수를 더하기 전에 S를 곱해주고 현재 항을 더해주는 것으로 나타내면 동일한 계산이 되므로 이 방식으로 계산을 하면 된다.

이에 따라 암호의 문자 c를 맨 앞자리부터 끝까지 확인하며 answer에 메모한 문자의 개수 S.length를 곱해주고 그 뒤에 현재 문자의 숫자 rank[c.code]를 더해준 이후 900528로 나누어주면 answer에 구하는 값이 저장되므로 출력하면 정답이 된다.

소스 코드

fun main() = with(System.`in`.bufferedReader()){
    val s = readLine()
    val password = readLine()
    val rank = IntArray(128)
    for(i in 0 until s.length){
        rank[s[i].code] = i + 1
    }
    var answer = 0L
    val mod = 900528L
    for(c in password){
        answer = (answer * s.length + rank[c.code]) % mod
    }
    println(answer)
}