[백준] 15829: Hashing

문제

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

---

코드

import java.io.*;

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 r = 31;
        int M = 1234567891;

        String line = br.readLine();
        long result = 0;
        long pow = 1;

        for (int i = 0; i < L; i++) {
            int num = line.charAt(i) - 'a' + 1;
            result += num * pow;
            pow = pow * r % M;
        }

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

---

풀이

처음 코드는 단순히 문제에서 말하는 거를 구현했다. 그리고 결과는 역시 50점...

import java.io.*;

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 r = 31;
        int M = 1234567891;

        int result = 0;

        String line = br.readLine();
        for (int i = 0; i < L; i++) {
            char str = line.charAt(i);
            int num = str - 'a' + 1;
            result += (int) (num * Math.pow(r, i));
        }

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

 

처음에는 시간 초과인 줄 알고 어떻게 해야지 줄일 수 있을까 고민했는데 그게 아니라 `result`가 `int`의 범위를 넘어서서 발생한 오류였다. 이런 유형의 문제는 종종 등장하는데, 매번 이 부분을 놓치게 된다...ㅎ

 

그래서 `result`를 `long` 타입으로 선언하고, 곱해질 값인 `r^i`를 관리하기 위해 `pow` 변수를 만들었으며 매 연산마다 `M`으로 mod 연산을 수행했다. 이렇게 하니 100점~~