[백준] 15829번 - Hashing

 

import java.util.Scanner;

public class p15829 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		String s = sc.next();
		int sum = 0;

		for (int i = 0; i < s.length(); i++) {
			sum += (int) (s.charAt(i) - 96) * Math.pow(31, i);
		}
		sum = sum % 1234567891;
		System.out.println(sum);
	}
}

 

이렇게 문제를 풀어보니 50점짜리 답안이라고 채점결과가 나왔다.

그래서 L < 50 인 케이스를 해결하기 위해서 출력을 하다보니 일정 수준이 넘어가다보면 숫자가 오버플로우 나서 음수값으로 표시됨을 알게 되었다.

그래서 연산을 하면서 sum과 pow연산을 하는 변수를 따로 두어 이 값들을 반복을 하면서 같은 모듈러 값으로 연산해주는 부분을 추가하여 제대로된 답을 구할 수 있게 되었다.

import java.util.Scanner;

public class p15829 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		String s = sc.next();
		long mod = 1234567891;
		long b = 1;
		long sum = 0;

		for (int i = 0; i < s.length(); i++) {
			long k = ((s.charAt(i) - 96) * b) % mod;
			sum += k;
			sum = sum % mod;
			b *= 31;
			b = b % mod;
		}
		System.out.println(sum);
	}
}