Loading [MathJax]/jax/output/CommonHTML/jax.js

1. 문제

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

 

26008번: 해시 해킹

첫째 줄에 비밀번호의 길이 N과 문자 종류의 개수 M, 정수 A가 주어진다. (1N,M,A5000000) 둘째 줄에 재현이가 알아낸 해시값 정수 H가 주어진다. (0H<M)

www.acmicpc.net

 

 

2. 문제 접근

  • 해당 문제는 해싱에 대해 묻고 있다.
  • 주목해야 할 점은 해싱하는데 사용하는 해시 함수 h(P)에 대해서이다. 문제에서 제시한 해시 함수는 아래와 같다.

h(P)=(P0A0+P1A1++PN1AN1)modM

  • 이때 P0 을 보자 A0 이 1이 되기 때문에 해당 부분을 적절히 이용하면 P0의 값을 적절히 변경함으로서 해시함수의 결과값을 변화시킬 수 있다.(나머지는 A의 값에 따라 달라지기 때문에 원하는대로 컨트롤하기가 힘들다.)
  • 그렇다면 문제에서 입력받은 해시 값 H를 도출해낼 수 있는 P0이 몇 개나 존재하는가인데 예제나 수를 해시함수에 대입하여 봄으로서 h(P)H가 될 수 있는 P0의 값은 하나만 존재하는 것을 알 수 있다.
  • 위에서 P0을 변경하여 해시함수의 값을 컨트롤 할 수 있다고 서술했다. 이는 곧 나머지 P 값들에 대해서는 상관없이 적절한 P0을 선정하여 해시함수에 넣을 수 있다면 항상 원하는 해시 값 H를 얻을 수 있다.
  • 따라서 H가 나올 수 있는 가짓수는 패스워도 문자의 종류 MP0를 제외한 나머지 P1부터 PN1까지 N1개를 선택하는 경우의 수가 되며 이는 곧 MN1이 된다.
  • 즉 답은 MN1mod1000000007이 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int A = Integer.parseInt(st.nextToken());

        int H = Integer.parseInt(br.readLine());

        long ans = 1L;

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

        System.out.println(ans);
    }
}

 

 

3. 정리

  • 해당 해시함수를 적절한 P0을 통해 컨트롤 할 수 있고, 입력으로 받는 해시값 H가 도출될 수 있는 P0의 값이 하나만 존재한다는 것을 알아내는 것이 중요했다.
  • 즉 입력으로 받은 값을 내는 답이 하나만 존재하며 그것만 알면 나머지 요소들은 어떠한 조합이 나와도 상관없기 때문에 경우의 수를 따져볼 때 M 종류의 문자를 N1번 선택하는 곱의 경우의 수를 생각하면 답을 도출할 수 있다. 

'DataStructure > Hash, map, set' 카테고리의 다른 글

HashMap의 원리와 설명  (1) 2023.03.16
프로그래머스 - 위장  (0) 2023.03.16
Programmers - 압축  (0) 2023.03.14
Hash, map의 문제 유형 탐구  (0) 2022.11.23
복사했습니다!