[백준] Hashing (BufferedReader, 모듈러 연산, 15829번, toCharArray(), Java)

▶ BufferedReader와 모듈러 연산을 활용한 간단한 문제가 있어 정리해보고자 합니다.

 

문제설명

입력 & 출력

나의 풀이

 

 

위 공식을 보면 시그마(Σ) 기호를 사용하여 0부터 l - 1까지 합을 구합니다. 공식을 보고 헷갈리면 밑에 힌트를 보면 보다 쉽게 이해할 수 있을 것입니다.

 

문자열 번호 * 31의 i번째 거듭제곱을 계속 더해주면 되는 문제입니다. 그러나 이번 문제는 모듈러 연산을 잘 모르면 50점 밖에 나오지 않는 문제입니다.

 

먼저 문제 접근 방식은 다음과 같습니다.

 

 

• 문자 값 변환
  • 문자열의 각 문자를 숫자로 변환합니다.
• 각 문자의 가중치 계산
  • 각 문자의 가중치는 해당 문자 값에 r의 거듭제곱을 곱한 값입니다. 
• 모든 문자의 가중치 합산
  • 모든 문자의 가중치를 더한 뒤, 결과를 M으로 나눈 나머지를 구합니다.

 

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int r = 31 , M = 1234567891;
        int N = Integer.parseInt(br.readLine());
        int sum = 0;

        char[] arr = br.readLine().toCharArray();

        for(int i = 0 ; i < arr.length ; i++){
            int ch = arr[i] - 96;
            sum += ch * Math.pow(r,i);
        }
        System.out.println(sum % M);
    }
}

50점 코드

 

---

따라서 모듈러 연산을 사용해서 구해야 합니다.

모듈러 연산 ❓
➡️
(A * B) mod C = (A mod C B mod C) mod C

 

모듈러 연산에 대해선 따로 포스팅에서 자세히 다뤄보도록 하겠습니다.

 

이제 "풀이"를 설명하자면 먼저 빠른 입력을 위해서 BufferedReader클래스를 사용하여 빠르게 입력을 받아줍니다.

 

그리고 거듭제곱 0은 항상 1이기 때문에 거듭제곱을 나타내는 pow변수를 1로 초기화해 줍니다.

 

문자열을 toCharArray() 메서드를 사용하여 문자로 받아 배열에 저장하고, 각 고유 번호로 바꿔줍니다.

 

그다음 20번째 줄 에서 모듈러 연산을 이용하여 거듭제곱 값에 r을 곱한 후, M으로 나눈 나머지를 취하는 데 이를 통해 정수 오버플로우를 방지하고 계산 결과를 M으로 나눠줬기 때문에 항상 M이하의 값으로 유지하게 됩니다.

 

예를 들어 설명하자면 

 

1➡️ 31 % 1234567891 = 31 ➡️ 31 * 31 % 1234567891 = 961

r^0 = 1

r¹ = 31

r² = 961 

 

길이가 3인 문자열이 들어왔을 때 pow의 초기값이 1이기 때문에 위와 같이 계산되게 됩니다.

 

 

 

참고 ❗

 

[Java] toCharArray() 메소드 알아보기 (문자열 ➡️ char배열)

[JAVA] 입출력, BufferedReader, StringTokenizer