백준 26008번 : 해시 해킹

알고리즘 문제 중 몇몇은 '비범한 일부'만이 바로 풀 수 있다.
그런 문제는 고민을 짧게 하고, 풀이를 보고 외워야 한다.

 

는 말을 들었던 기억이 났다.
이 문제를 풀면서 그 말이 무슨 말인지 깨닳았다.

문제

---

26008번: 해시 해킹 (acmicpc.net)

26008번: 해시 해킹

해싱 함수와 그 해싱 함수의 결과값 h(P)가 주어졌을 때 이를 만족하는 비밀번호의 개수를 구하는 문제

 

아이디어

---

해싱함수에 대한 문제이므로 해시 맵을 사용해서 풀이하려 했지만 답이 나오지 않았다.
약 3-4시간을 고민했던 것 같다.

이 문제는 해시 컬렉션을 이용하는 문제가 아니라,
'나머지'에 대한 조건을 얼마나 영리하게 파악했는지를 확인하는 문제였다.

• 주어진 수식에서 P_0가 될 수 있는 범위는 0~M-1이다.
• 따라서 P_0을 제외한 수가 고정되어있다고 할 경우 주어진 해시값을 만족하는 비밀번호는 1개이다.
• P_0을 제외한 수의 조합은 M**(N-1)개이다.
• M**(N-1)개의 조합에서 조합 당 하나의 숫자만 주어진 해시값을 만족한다.
• 따라서 어떤 해시값이 주어지더라도, M**(N-1)을 리턴하기만 하면 되는 거였다.

 

코드

---

public static void main(String[] args) {
    // 형식대로 입력받기
    Scanner scanner = new Scanner(System.in);
    int N = scanner.nextInt(); // 비밀번호의 길이
    int M = scanner.nextInt(); // 문자의 종류 (0~M-1) 사이
    int A = scanner.nextInt(); // 해시값의 제곱과 mod 연산에 사용됨
    int H = scanner.nextInt(); // 해시값

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

    // 오버플로우 발생
    /*
    long answer = 1L;
    for(int i = 0; i<N-1; i++){
        answer *= M;
    }
    System.out.println(answer%1000000007L);
     */

    // 오버플로우 발생
    // System.out.println((int)Math.pow(M,(N-1)) % 1000000007);
}

 

교훈

---

• ❗알고리즘 문제는 45분 이상 고민하지 말자. ❗
• 해결 방법이 받아들일 수 없을정도의 아이디어이더라도, 시간을 더 잡아먹기보다 빠르게 수긍하고 넘어가자.
• int를 쓰면 1000,000,000(10억) 이상의 수를 계산할 수 없으므로, 5000**5000같은 수를 계산할 때는
  Math(M, N-1) 을 한 다음 나머지 연산 → 오버플로우 발생
  for문을 사용해서 곱하고, 중간중간 %를 사용해서 오버플로우 방지하는 형태가 되어야 한다.