알고리즘 문제 풀이를 블로그에 올리는 이유는 풀이, 코드를 기록하기 위함이니
앞으로 문제를 다 긁어오기보다 링크만 두고 풀이가 잘 보이도록 포스팅 할 예정입니다!

📄 문제

[백준] Hashing

---

👩‍💻 풀이

1. 문제 이해

이 문제는 입력된 문자열을 한 글자씩 떼어 숫자로 변환(a=1, b=2, ..., z=26)하고,
위 식처럼 하나씩 31i를 곱하여 총합을 구한 뒤, mod M(M=1234567891) 연산을 한 값을 구하는 문제이다.

2. 풀이

• 이 문제는 특이하게 채점 결과로 50점이 나온다..! (틀린 것도 아니고 맞은 것도 아니고 50점;;)
• 나또한 처음에 50점이 나왔었는데, 진행중인 코테 스터디 팀원분께서 해답을 찾아주셨다..!👍

  [ 50점짜리 답안이 나오는 이유! ]
  
  원인 1 : Math.pow() 메소드의 사용
  Math.pow() 는 거듭제곱 연산값을 double로 반환하는 메소드
  그런데! 숫자가 많이 커지면, 일정 부분 숫자를 올림 처리하여 정확하지 않은 값을 반환!!!
  때문에 숫자가 많이 켜졌을 경우, 올림 처리된 값을 곱하여 오류 발생
  아래와 같이 pow를 변수로 만들고 이를 반복문 내부에서 계속 갱신해주면 해결됨
  
  
  원인 2 : mod 연산 미포함
  혹시 위 방법으로 해결이 되지 않는다면,
  pow와 hash 결과 값을 M 값으로 나누어주는 mod 연산을 했는지 확인
  거듭제곱 연산이 포함된 만큼 pow와 hash 값이 매우 커질 수 있기 때문에 두 값 모두 mod 연산을 해주어야 함

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int L = Integer.parseInt(br.readLine());
        int M = 1234567891;
        String string = br.readLine();

        long hash = 0;
        long pow = 1;
        for(int i = 0; i < L; i++) {
            hash += (string.charAt(i) - 96) * pow;
            pow = (pow *= 31) % M;
        }

        System.out.println(hash % M);
    }
}