[백준] 알고리즘 분류(문자열,JAVA)15829번, Hashing

문제 링크

 

15829번: Hashing

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 문자열에는 소문자 알파벳만 주어집니다.

2. 문제와 동일한 해시함수가 존재한다고 할 때 출력되는 결과를 출력합니다.

3. 문자열은 L의 길이만큼 주어집니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 모든 글자들을 해시함수에 적용을 진행합니다.

 

3. 모든 문자열이 해시함수가 적용된 후 결과를 출력합니다.

 

해시함수

 

문제에서 설명하는 해시함수를 그대로 적용하면 됩니다.

 

알파벳의 순서에 따라 31의 거듭제곱한 뒤 나머지로 1234567891을 진행합니다.

 

Ex)

단어 : aa

해시함수 계산 : a(1) * 1 + a(1) * 31¹ = 32 mod 1234567891 = 31

 

해시 함수의 곱을 모두 더한 뒤에 나머지를 구하면 Large TestCase에서 실패할 것입니다.

 

왜냐하면 더하는 과정 중에서 오버플로우가 발생하여 올바른 값이 나오지 않을 것이기 때문입니다.

 

저는 모듈러 연산을 이용해서 오버플로우가 발생하는 것을 방지하였습니다.

 

모듈러 연산이란?

모듈러 산술 - 위키백과, 우리 모두의 백과사전

연산을 진행한 후 나머지를 구하는 것에서 모두 나머지를 구하여 계산한 결과가 같다는 공식입니다.

 

(a * b) mod c = ((a mod c) * (b mod c)) mod c 

 

위 식을 이용해서

해시함수에 곱하기를 진행할 때마다 나머지를 구해서 31의 제곱을 진행할 때 오버플로우가 발생하는 것을 방지할 수 있습니다.

 

31² = ((31 mod 1234567891) * (31 mod 1234567891)) mod 1234567891

 

 

예제입력 2.

 

1. 입력된 정보를 저장합니다.

 

 L = 3

문자열 : zzz

 

2. 모든 글자들을 해시함수에 적용을 진행합니다.

 

zzz

 

※나머지를 구하는 값 1234567891을 div로 표현하겠습니다.

 

1번째 z

z : ((26 mod div) * (1 mod div)) mod div = 26

 

2번째 z

z : ((26 mod div) * (31 mod div)) mod div = 806

 

3번째 z

z : 26 * 31²

((26 mod div) * ((31 mod div)) * (31 mod div)) mod div = 24986

 

3. 모든 문자열이 해시함수가 적용된 후 결과를 출력합니다.

 

(26 + 806 + 24986) mod div = 25818을 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• for문을 통해서 문자열을 해시함수에 적용시켰습니다.
• 해시함수에 적용할 때 모듈러 연산으로 인하여 나머지를 지속적으로 구해주었습니다.
• 해시함수가 종료된 뒤 결과를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int L = Integer.parseInt(br.readLine());	//입력되는 L
        int div = 1234567891;		//나머지 구하는 값
        long result = 0;		//결과값
        String input = br.readLine();		//입력되는 문자열
        //문자열 탐색하여 해시 함수 적용시켜 변경하기
        for(int i=0;i<L;i++){
            long temp = 1;
            //모듈러 연산에 의해 곱하기를 진행할 때마다 나머지 구하기 진행!
            for(int j=0;j<i;j++)
                temp = (temp * 31) % div;
            result += ((input.charAt(i)-96) * temp)% div;
            result %= div;		//모듈러 연산으로 더하였을 때도 나머지 구하기 진행!
        }
        bw.write(result + "");	//해시 함수 결과를 BufferedWriter 저장
        bw.flush();			//결과 출력
        bw.close();
        br.close();
    }
}