[백준/BOJ] 15829번 : Hashing (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

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

15829번: Hashing

---

- 문제 -

 

난이도 브론즈 2 문제이다.

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

소문자 알파벳이 오면 a부터 z까지 1~ 26까지의 값을 가진다고 한다. 그렇다면 여기서 바로 생각할 것은 아스키 코드이다. a의 아스키 코드는 97이다. a가 1이란 값을 가지려면 a - 96을 해주면 된는 것이다. 그리고 맨 앞자리부터 31의 제곱수를 곱해준다. 3 abc 면 1 * (31의 0제곱) + 2 * (31의 1제곱) + 3 * (31의 2제곱)을 해주면된다. 그리고 그 값에 1234567891을 나눈 나머지를 구하면 된다.

 

두가지 방법으로 풀 것이다. 엄밀히 말하면 푸는 방식은 같고, 쓰이는 자료형이 다르다 하는게 맞을 것 같다.

1. BigInteger로 푸는 방법

2. long형으로 푸는 방법

 

친구가 이 문제를 먼저 풀고서 했던 말이 있다. 질문게시판에서 사람들이 49제곱은 자바에서 표현할 수 없다고. 물론 적은 사람이 그런 의미로 말한 건 아닐 수 있지만 친구는 부동소수점처럼 그런걸로 이해했다고 한다. 하지만 여기서 말하는 것은 최대 길이가 50이면 31의 49제곱까지 나올 건데 long형의 범위로는 31의 49제곱을 담을 수가 없다. 그렇기때문에 long형으로 풀 경우 31의 제곱을 구할때마다 1234567891을 나눠준다. 그렇게 해서 더해진 값은 long의 범위를 넘어서진 않을 것이다. 1234567890을 50번 더한다고 넘진 않은다.(예시일뿐 저렇게 더하진 않는다) 어쨋든 그렇게 나온 값은 1234567891을 넘을 수 있으니 마지막에 1234567891을 나눈 나머지를 구하자.

 

BigInteger는 위같은 문제를 걱정할 필요 없다. 무한한 범위이기 때문에 31의 1000만 제곱이 와도 가능하다.

 

코드를 보자.

 

---

-풀이-

1. BinInteger을 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

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());
		String S = br.readLine();
		BigInteger result = new BigInteger("0");
		for(int i = 0; i < L; i++) {
        //좀 길지만 result에 현자 자릿수의 알파벳에서 정수 1~26중 해당 값을 더해주고
        //그 값에 31의 i제곱한 값을 곱해주는 것이다.
			result = result.add(BigInteger.valueOf(S.charAt(i) - 96).multiply(BigInteger.valueOf(31).pow(i)));
		}
        //출력할때는 1234567891을 나눠주자.
		System.out.println(result.remainder(BigInteger.valueOf(1234567891)));
	}

}

 

2. long으로 푼 방법

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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());
		String S = br.readLine();
		long result = 0;
		long pow = 1;
		for(int i = 0; i < L; i++) {
			result += ((S.charAt(i) - 96) * pow);
			//pow는 31을 매번 곱해준다. 곱해줄때마다 1234567891을 나눠주면 long을 넘지 않을 것이다.
			pow = (pow * 31) % 1234567891;
		}
		System.out.println(result % 1234567891);
	}

}

---

-결과-

1번 방법

2번 방법

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.