1. Problem 📃
https://www.acmicpc.net/problem/15829
[ 문제 ]
APC에 온 것을 환영한다.
만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다.
해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정의한다.
해시 함수는 무궁무진한 응용 분야를 갖는데, 대표적으로 자료의 저장과 탐색에 쓰인다.
이 문제에서는 여러분이 앞으로 유용하게 쓸 수 있는 해시 함수를 하나 가르쳐주고자 한다.
먼저, 편의상 입력으로 들어오는 문자열에는 영문 소문자(a, b, ..., z)로만 구성되어있다고 가정하자.
영어에는 총 26개의 알파벳이 존재하므로 a에는 1, b에는 2, c에는 3, ..., z에는 26으로 고유한 번호를 부여할 수 있다.
결과적으로 우리는 하나의 문자열을 수열로 변환할 수 있다.
예를 들어서 문자열 "abba"은 수열 1, 2, 2, 1로 나타낼 수 있다.
해시 값을 계산하기 위해서 우리는 문자열 혹은 수열을 하나의 정수로 치환하려고 한다.
간단하게는 수열의 값을 모두 더할 수도 있다.
해시 함수의 정의에서 유한한 범위의 출력을 가져야 한다고 했으니까 적당히 큰 수 M으로 나눠주자.
짜잔! 해시 함수가 완성되었다.
이를 수식으로 표현하면 아래와 같다.
해시 함수의 입력으로 들어올 수 있는 문자열의 종류는 무한하지만 출력 범위는 정해져있다.
다들 비둘기 집의 원리에 대해서는 한 번쯤 들어봤을 것이다.
그 원리에 의하면 서로 다른 문자열이더라도 동일한 해시 값을 가질 수 있다.
이를 해시 충돌이라고 하는데, 좋은 해시 함수는 최대한 충돌이 적게 일어나야 한다.
위에서 정의한 해시 함수는 알파벳의 순서만 바꿔도 충돌이 일어나기 때문에 나쁜 해시 함수이다. 그러니까 조금 더 개선해보자.
어떻게 하면 순서가 달라졌을때 출력값도 달라지게 할 수 있을까?
머리를 굴리면 수열의 각 항마다 고유한 계수를 부여하면 된다는 아이디어를 생각해볼 수 있다.
가장 대표적인 방법은 항의 번호에 해당하는 만큼 특정한 숫자를 거듭제곱해서 곱해준 다음 더하는 것이 있다.
이를 수식으로 표현하면 아래와 같다.
2. Input ⌨️
[ 입력 ]
첫 줄에는 문자열의 길이 L이 들어온다.
둘째 줄에는 영문 소문자로만 이루어진 문자열이 들어온다.
입력으로 주어지는 문자열은 모두 알파벳 소문자로만 구성되어 있다.
3. Output 🖨
[ 출력 ]
문제에서 주어진 해시함수와 입력으로 주어진 문자열을 사용해 계산한 해시 값을 정수로 출력한다.
4. Example 📚
[ 입출력 예시 ]
| 예제 입력 | 예제 출력 |
|---|---|
| 5 abcde | 4739715 |
| 3 zzz | 25818 |
| 1 i | 9 |
5. Solution 🔑
- 상수 선언으로 M값과 r값을 입력 받는다.
문자열의 길이를 입력 받을 변수(L)을 입력받는다.
- 나온 해쉬값을 누적 시켜줄 변수(sum)을 선언한다.
- 자릿수(i)에 따른 M의 i제곱을 해줄 메서드(pow)를 정의해준다.
n제곱은 값을 n번 곱했다는 얘기이므로, 재귀함수로 제곱할 수가 1이 될 때까지 매개변수를 하나씩 줄여나가면 된다. 매개변수에 0이 들어가면 본인 자신(r)만을 반환한다.
그런데 이때, 31의 제곱이 정수 범위를 넘어갈 수 있으므로, 미리 정의해 둔 상수 M으로 나머지 값을 구하게하여, 범위를 넘지 않도록 돕는다.
- 문자열 길이 L만큼 for문을 돌려 하나 하나 문자(charAt())를 확인하며, a가 1의 값을 띄고 있으므로 아스키코드 97이 아닌 96을 빼준다. 그 후 인덱스 i는 제곱 수를 나타내는것 이므로, pow메서드를 호출하여 매개변수를 i로 넘겨주고 반환된 값과 해당 문자열 값을 곱하여 sum변수에 누적시킨다.
- 최종적으로 나온 sum을 출력하는데 이때 M으로 한 번 더 나머지를 구하는 나눗셈으로 나누어 범위값에 오류가 나지 않도록 해주고 값을 출력한다.
6. Code 💻
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
publ1ic class Main {
final static int M = 1234567891;
final static int r = 31;
static long pow(int i) {
return i==0?1:r*pow(i-1)%M;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int L = Integer.parseInt(br.readLine());
long sum = 0;
String str = br.readLine();
for(int i=0; i<L; i++) {
sum += (str.charAt(i)-96) * pow(i);
}
System.out.println(sum%M);
}
}