[백준 골드3] 26008번 해시 해킹 / Java

백준

문제

문제 설명

그린닷컴의 운영자 연두는 비밀번호를 평문 그대로 저장하는 과오를 뒤로하고, 이제부터 암호에 해시 함수를 적용해 저장하려고 한다. 연두가 아는 해시 함수라고는 알고리즘 문제 풀이에 많이 사용되는 롤링 해시 함수밖에 없기 때문에 이것을 응용하여 사용하기로 했다.

 

그린닷컴의 비밀번호 규칙은 꽤 특이한데, 길이가 정확히 N이어야 하며, 비밀번호를 이루는 문자는 지정된 M개의 문자 중 하나여야 한다.

 

따라서, 사용 가능한 각 문자를 0부터 차례대로 정수에 대응시키면, 비밀번호를 길이가 N이고 모든 원소가 0이상 M−1이하인

배열 P=[P0,P1,…,PN−1]로 나타낼 수 있다.

 

이렇게 비밀번호를 배열 P로 나타낸 후, 미리 정해진 정수 A를 이용하여 다음과 같은 해시 함수 h를 적용한다.

 h(P)=(P0⋅A0+P1⋅A1+...+PN−1⋅AN−1)mod M

 

예를 들어, 배열 P=[10,30,20],A=7,M=55인 경우를 생각해보자.

이 경우 h(P)=(10⋅70+30⋅71+20⋅72) mod 55 = 45이다. 여기서 mod는 나머지 연산으로 1200=21⋅55+45이므로

1200 mod 55=45이다. 따라서 해시값은 항상 0 이상 M−1 이하의 정수이다.

 

그린닷컴 관리자 계정의 비밀번호 해시값을 해킹한 재현이는, 이 해시값으로 실제 비밀번호가 뭐였는지 역추적해보려고 한다. 하지만 그린닷컴에서 사용 가능한 비밀번호는 M^N개나 있고, 이 중 과연 알아낸 해시값과 일치하는 비밀번호는 몇 개나 될지 궁금해졌다. 여러분이 이것을 대신 구해주자.

입력

첫째 줄에 비밀번호의 길이 N과 문자 종류의 개수 M, 정수 A가 주어진다. (1≤N,M,A≤5000000)

둘째 줄에 재현이가 알아낸 해시값 정수 H가 주어진다. (0≤H<M)

출력

주어진 해시값을 갖는 비밀번호의 개수를 출력한다. 출력하는 값이 너무 커질 수 있으므로, 이것을 1000000007(=10^9+7)로 나눈 나머지를 출력한다.

아이디어

처음에는 단순하게 "그냥 조합에서 하나씩 처리해서 나온 해쉬값과 주어진 해쉬 값을 비교하면 되겠지?" 하고 예시 입출력을 봤는데, 2번째 예시에 나와있는 5000000을 보고 생각을 접게 됐다.

 

그 다음으로 들었던 생각은 "DP를 하는 것처럼 점화식을 구해서 구해야하나?"라는 생각이었다.

우선 A^0은 1이니까, h(p) = {P0 + (P1*A^1 + ...)} mod M 으로 P0를 따로 뺄 수 있다.

여기서 생각해볼 점은 h(p)의 값은 0~M-1 중에 하나일 것이다. -> 총 M개

그리고 P의 배열을 N만큼의 길이를  가지니까, 총 조합으로는 M^N개 만큼의 비밀번호의 조합들이 존재하게 될 것이다.

 

하지만, 여기서 알 수 있는 점은 hash code는 mod 연산이 끝난 후의 값이므로, 0~M-1의 값이다. 총 M개만큼이 나오게 되므로,

M^N / M = M^(N-1)이 문제에서 입력으로 주어지는 h의 값과 동일할 것이다.

 

하지만 수의 범위가 int형의 범위를 넘어가게 될 수도 있으므로, 곱하고 mod (10^9+7)를 해주면 특정 값의 범위는 넘게 되지 않을 것같다.

소스코드

// 백준 26008번 해시 해킹 골드3

import java.util.*;

class Main{
    public static void main(String[] args) {

        int DIVIED = 1000000007;
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int A = sc.nextInt();

        int H = sc.nextInt();
        long answer = 1L;
        for(int i = 0 ; i <N-1;i++ ){
            answer = (answer * M) % DIVIED;
        }
        System.out.println(answer);

    }
}

결과

정답

성능 요약

메모리: 17760 KB, 시간: 284 ms

후기

처음에 수학적으로 접근하지 않아, 중요한 알고리즘을 떠올리기까지 많은 시간이 걸렸던 것같다.

하지만 수학적으로 접근해보면, 금방 알아 차릴 수 있는 문제였던 것같다.