[백준] 15829번 : Hashing - JAVA

 

 

15829 Hashing

 

 

이번 문제는 친절하게도 문제에서 어떻게 연산을 하라고 다 알려주고 있지만 필자는 처음에 50점을 맞았다...

 

필자의 처음 생각으로는 알파벳 a가 1이 나와야 하고 a의 아스키코드 값이 96이니까 -95를 더했고

$a_i * r^i$ 이 수식은 반복문을 사용하며 제곱의 경우 Math 클래스의 pow 메서드를 사용하면 되겠다고 생각을 하였다.

그러나 오버플로우가 발생하여 50점이 나왔다.

 

실패한 소스 - 오버플로우 발생

final int NUMBER = 31;
final int M = 1234567891;

int l = Integer.parseInt(br.readLine());
String str = br.readLine();
long sum = 0L;

for (int i = 0; i < str.length(); i++) {
    // Math.pow부터 이미 오버플로우가 발생함
    sum += (str.charAt(i) - 96) * ((long) Math.pow(NUMBER, i));
}

System.out.println(sum % M);

 

어떻게 보면 당연한 것을 놓쳐버렸다...

 

위와 같이 Math 클래스의 pow 메소드를 사용하는 경우 오버플로우가 발생하여 직접 제곱을 해주는 방식으로 변경하였고 100점으로 통과하게 되었다.

 

성공한 소스

public class Main {

    public static void main(String[] args) throws IOException {
        final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        final StringBuilder sb = new StringBuilder();
        final int NUMBER = 31;
        final int M = 1234567891;

        int L = Integer.parseInt(br.readLine());
        String str = br.readLine();
        long sum = 0L;
        long pow = 1L;

        for (int i = 0; i < L; i++) {
            sum += (str.charAt(i) - 96) * pow;
            pow = (pow * NUMBER) % M;
        }

        sb.append(sum % M);

        System.out.println(sb);
        br.close();
    }

}

 

 

쉬워보인다고 가볍게 넘어가지 말고 다시 한번 살펴보는 습관을 가지자!