[백준] 15829번 : Hashing - Java

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

---

---

• 문제

---

---

• 풀이

- 조건에 맞춰서 해시함수를 작성한되, Large 케이스에 유의한다.

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int L = sc.nextInt();
		String s = sc.next();
		long arr[] = new long [L];
		long square = 1;
		long sum = 0;
		
		for (int i = 0; i < L; i++) {
			int tmp = (s.charAt(i) - 'a') + 1;
			arr[i] = tmp * square;
			square = (square * 31) % 1234567891;
		}
		
		for (int j = 0; j < L; j++) {
			sum = (sum + arr[j]) % 1234567891;
		}
		
		System.out.println(sum);
		
		sc.close();
	}
}				num /= 10;			}						if (sum + i == N) {				result = i;				break;			}		}				System.out.println(result);		sc.close();	}}<\/code><\/pre>

 

 

문자열의 길이에 맞는 배열을 생성한다. 단 큰 숫자를 받기 위해 long타입을 이용한다.

해시 함수 조건에 맞게 코드를 작성하되, square에 주의한다.

제곱이 될 수록 수가 커져 long의 범위도 벗어나므로 제곱수에도 M인 1234567891을 나눠준다.

 

※ A+B = C라고 가정할 때, (A+B) % M = C % M을 이용한 것이다.