1. 문제
https://www.acmicpc.net/problem/26008
26008번: 해시 해킹
첫째 줄에 비밀번호의 길이 N과 문자 종류의 개수 M, 정수 A가 주어진다. (1≤N,M,A≤5000000) 둘째 줄에 재현이가 알아낸 해시값 정수 H가 주어진다. (0≤H<M)
www.acmicpc.net
2. 문제 접근
- 해당 문제는 해싱에 대해 묻고 있다.
- 주목해야 할 점은 해싱하는데 사용하는 해시 함수 h(P)에 대해서이다. 문제에서 제시한 해시 함수는 아래와 같다.
h(P)=(P0∗A0+P1∗A1+⋯+PN−1∗AN−1)modM
- 이때 P0 을 보자 A0 이 1이 되기 때문에 해당 부분을 적절히 이용하면 P0의 값을 적절히 변경함으로서 해시함수의 결과값을 변화시킬 수 있다.(나머지는 A의 값에 따라 달라지기 때문에 원하는대로 컨트롤하기가 힘들다.)
- 그렇다면 문제에서 입력받은 해시 값 H를 도출해낼 수 있는 P0이 몇 개나 존재하는가인데 예제나 수를 해시함수에 대입하여 봄으로서 h(P)가 H가 될 수 있는 P0의 값은 하나만 존재하는 것을 알 수 있다.
- 위에서 P0을 변경하여 해시함수의 값을 컨트롤 할 수 있다고 서술했다. 이는 곧 나머지 P 값들에 대해서는 상관없이 적절한 P0을 선정하여 해시함수에 넣을 수 있다면 항상 원하는 해시 값 H를 얻을 수 있다.
- 따라서 H가 나올 수 있는 가짓수는 패스워도 문자의 종류 M을 P0를 제외한 나머지 P1부터 PN−1까지 N−1개를 선택하는 경우의 수가 되며 이는 곧 MN−1이 된다.
- 즉 답은 MN−1mod1000000007이 된다.
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 종류의 문자를 N−1번 선택하는 곱의 경우의 수를 생각하면 답을 도출할 수 있다.
'DataStructure > Hash, map, set' 카테고리의 다른 글
HashMap의 원리와 설명 (1) | 2023.03.16 |
---|---|
프로그래머스 - 위장 (0) | 2023.03.16 |
Programmers - 압축 (0) | 2023.03.14 |
Hash, map의 문제 유형 탐구 (0) | 2022.11.23 |