Hashing(15829)

Hashing(15829)

import java.io.*;
import java.util.*;

public class Main{
  public static void main(String[] args) throws IOException {
      
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    
    int strLength = Integer.parseInt(br.readLine());
    String str = br.readLine();
    
    char[] ch = str.toCharArray();
    
    long M = 1234567891;
    long r = 1;
    long sum = 0;
    
    for(int i = 0; i < strLength; i++){
      sum += ((ch[i] - 96) * r) % M;
      r = r * 31 % M;
    }
    
    sb.append(sum % M).append(" ");
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
}

풀이과정

1) 이 문제는 간단히 생각하고 풀면 50점, 즉 작은 범위에서만 정답이 될 것이다.
2) 이유는 큰 범위로 가는 경우 50개의 문자가 들어올 수 있는데 그렇다면 마지막 문자는 (문자 번호 * 31^49)이 된다.
3) 아무리 long long을 쓰더라도 범위를 벗어날 수 밖에 없고 overflow가 발생하기 때문이다.
4) 저기서 mod M(% M)의 연산 규칙을 알게 되면 범위를 벗어나지 않고 풀 수 있다.
5) 백준(10430) 나머지 를 보면 모듈러스 연산자의 응용을 배울 수 있게 된다.

• 성공
• 메모리 : 14212 KB
• 시간 : 124 ms