코딩 테스트 풀이 5 - 해시 해킹

✔ 문제

https://www.acmicpc.net/problem/26008

💡 접근 방법

위 수식은 문제에서 준 해시 함수이다. 잘 살펴보면, $A^0$ 은 언제나 $1$ 이라는 점과, $h(P)$ 의 값은 $mod$ 연산으로 인해 $0$ ~ $M-1$ 의 값을 가지게 된다는 것을 알 수 있다. 그래서 $h(P)$ 의 값이 주어진다면 (고정된다면), $P_0$ 를 그에 맞춰 조절해주는 것으로 $P_1 ... P_{N-1}$ 이 무엇이 되든 상관이 없다는 점을 알 수 있다.

예로 들어서, 문제의 예시처럼 $M = 55$ 라고 하자. 그리고, $P_1 A^1 + ... + P_{N-1} A^{N-1}$ 의 값이 미지의 정수 $X$ 라고 하자. 그럼 단순히 $P_0$ 를 $55-X$ 로 만들어 주면 된다. 이처럼, 문제에서 결과해시값을 준다면(고정한다면) $P_0$ 만 적절히 조절해주면 나머지 비밀번호값들은 자유도를 가지므로, 결국 해시값과 일치하는 비밀번호의 경우의 수는 $M^{N-1}$ 이 된다.

⭐ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int pwLength = Integer.parseInt(st.nextToken());
        int typeNum = Integer.parseInt(st.nextToken());

        BigInteger bg = new BigInteger(String.valueOf(typeNum));
        BigInteger exp = new BigInteger(String.valueOf(pwLength-1));
        BigInteger mod =  new BigInteger(String.valueOf((int)Math.pow(10,9)  + 7));
        
        System.out.println(bg.modPow(exp,mod));
    }
}

🧩 BigInteger ?

사실 $M^{N-1}$ % ($10^9 - 7)$ 만 하면 된다고 생각해서 처음에 내가 짠 코드는 이런 형태였다 :

int pwNum = ((int)Math.pow(typeNum,pwLength-1)) % ((int)Math.pow(10,9)  + 7);

하지만 문제에서 준 테스트 케이스인 $(5000000, 5000000,5000000)$ 에는 올바른 결과값을 도출하지 않았다. 문제는 지수 연산에서 Integer의 최대값을 넘어가는 것이었다. 이 문제를 해결할 수 있는 방법은 두 가지이다.

1. 반복문을 사용해 지수 연산을 하고, 매 반복문 안에서 % 연산을 할 수 있다. % 연산은 중간에 해도 같은 결과값을 주기 때문이다.
2. 두번째 방법은 BigInteger 클래스를 쓰는 것이다. 인터넷에서 찾은 잘 모르는 방법이었기 때문에 실제 코드는 이 방법을 써서 제출하였다.

BigInteger 클래스는 클래스명처럼 아주 큰 정수를 다룰 때 쓰는 클래스이다. 위 문제처럼, 정수의 범위를 넘어갈 가능성이 있는 케이스에 쓸 때 효과적인데, 이유는 BigInteger 클래스가 내부적으로 문자열 형태로 이루어져 있어서, int, long 자료형 byte가 넘어가는 숫자에 대해서도 오류를 일으키지 않기 때문이다.

문제에서 쓴 modPow 외에도 , 기본적인 사칙연산 (add,subtract,multiply,divide) 를 비롯해 여러 수학적 계산을 할 수 있다.

비슷하게, BigDecimal 클래스가 있는데, float 과 double 자료형의 소수점 정밀도가 완벽하지 않아 생기는 문제를 해결할 수 있는 방법이다.