자료구조 5/11 - HashMap

연관문제

해시 해킹 - 백준 26008번

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        String[] s = (br.readLine()).split(" "); // m, n, a
        int N = Integer.parseInt(s[0]);
        int M = Integer.parseInt(s[1]);
        int A = Integer.parseInt(s[2]);
        int hash = Integer.parseInt(br.readLine());

        Long answer = 1L;
        // M ^ (N - 1) % 1_000_000_007
        for (int i = 0; i < N - 1; i++) {
            answer = (answer * M) % 1_000_000_007;
        }

        System.out.println(answer);
    }
}

• 까다로웠던 부분은 큰 숫자를 다루는 부분이었다. 백준의 테스트 케이스에는 M과 N이 각각 500만 인 케이스가 있었다. 5백만을 5백만 제곱을 한다는게 자바로는 할 수 없을 것 같아서 이걸 어떻게 처리해야 할지에 대한 고민이 가장 컸다.

• 하지만 작은 숫자를 예로 들어서 계산을 해보니깐 풀이를 나눠서 할 수 있겠다라는 것을 알았다.

• 예를 들어 4 의 200 승을 15로 나눈 나머지를 찾아야 할 때, 우리는 4의 199승을 15로 나눈 나머지만 필요할 수 도 있다. 이런식으로 아래로 나아가다보면 우리는 4의 1승 즉 4를 15로 나눈 나머지만 알면 된다는 것이다.

예를들어
("4 x 4 x 4 x 4" x 4) % 15 의 경우에서
앞부분 4를 네번곱한 부분을
먼저 15로 나누어
(15 x 몫 + 나머지) x 4 로 바꾼다면

(4 x 4 x 4 x 4 x 4) = (15 x 몫 x 4 + 나머지 x 4) 이므로
자연스럽게 (15 x 몫) 은 15의 배수이기 때문에 15로 딱 나누어 떨어지기 때문에
우리는 15로 나누어 떨어지지 않았던 '나머지'부분 만을 남은 4로 곱한뒤 15로 나누어 보면 된다는 컨셉이다.

그 계산이 위의 코드엔 아래와 같이 표현되어 있다.

for (int i = 0; i < N - 1; i++) {
    answer = (answer * M) % 1_000_000_007;
}

제곱 계산을 나머지 부분만 따서 나머지 만을 계산한다면
500만의 500만 제곱을 10억7 로 나누는 케이스도 계산해볼 수 있는 것이다.