[Java] 백준(브론즈-2) 15829번 - Hashing

문제 풀이

---

이번 문제는 단순한 구현 문제이다.

아이디어 도출

이번 문제는 서브테스크 유형의 문제라 Small Case를 충족하면 50점, Large Case까지 충족하면 100점을 받을 수 있다.

처음엔 단순하게 생각하여 풀었더니 문자열 길이 50까지의 범위를 고려하지 못해 Small Case만 충족되어 50점을 달성하였다. 어떻게 Large Case까지 충족하여 100점을 받을 수 있을까 고민하고 개선하여 100점을 받았는데 그 아이디어를 살펴보자.

문제풀이를 위한 핵심 아이디어 2가지는 다음과 같다.

1. 모듈러 연산
2. 수의 범위

모듈러 연산

이번 문제에서 100점을 받기 위해서는 모듈러 연산의 성질을 잘 이해해야 한다.

1. (A + B) mod C = (A mod C + B mod C) mod C
2. (A - B) mod C = (A mod C - B mod C) mod C
3. (A * B) mod C = (A mod C * B mod C) mod C

위 성질을 통해 아래 연산식이 가능하다는 것을 알 수 있다.

a2r2 mod M = (a2 mod M * r2 mod M) mod M
r2 mod M = (r mod M * r mod M) mod M
r3 mod M = (r2 mod * r mod M) mod M
r4 mod M = (r3 mod M * r mod M) mod M

수의 범위

또한, Math.pow() 메서드를 사용하여 31의 제곱수를 곱해주는 방식으로 구현했지만 Math.pow(31, 49)까지 간다면 long형의 범위도 벗어나기 때문에 해당 메소드를 사용하지 않고 pow를 일일이 곱해주면서 모듈러 연산을 통해 문제에서 제시한 M(=1234567891)보다 크기를 줄여가야 한다.

그래서 pow로 사용하는 변수와 해시 함수의 결과값을 더해줄 결과값 변수는 long 형으로 선언해서 사용해야 한다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

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

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));
        
        Map<Character, Integer> hm = new HashMap<>();
        for(int i=97; i<123; i++) {
            hm.put((char)i, i-96);
        }

        int M = 1234567891;

        int L = Integer.parseInt(br.readLine());
        String str = br.readLine();

        long result = 0;
        long pow = 1;

        // Math.pow() 메서드를 사용하면 long형의 범위를 벗어나기 때문에 Large 케이스를 통과할 수 없다.
        for(int i=0; i<L; i++) {
            char alph = str.charAt(i);
            result += (hm.get(alph) * pow) % M;
            pow = (pow * 31) % M;
        }

        bw.write((result%M)+"\n");

        bw.close();
        br.close();
    }    

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.