백준[15829]번 : Hashing ( JAVA )

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

15829번: Hashing

---

Code

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
import java.util.HashMap;

public 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));
		
		int n = Integer.parseInt(br.readLine());
		
		String arr = br.readLine();
		
		HashMap<Character,Integer> map = new HashMap<>();
		
		for(int i=0;i<26;i++) {
			map.put((char)(i+97),i+1);
		}
		
		BigInteger bi1 = new BigInteger("0");
		BigInteger r = new BigInteger("31");
		BigInteger m = new BigInteger("1234567891");
		
		for(int i=0;i<n;i++) {
			char ch = arr.charAt(i);
			BigInteger ch2 = BigInteger.valueOf(map.get(ch));
			bi1 = bi1.add((r.pow(i).multiply(ch2)).mod(m));
		}
		
		bi1 = bi1.mod(m);
		
		bw.write(bi1+"");
		
		br.close();
		bw.close();
	}
}

---

처음에 문제를 풀 때에는 50점을 맞았다.

아래는 계속 50점을 맞은 코드이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.StringTokenizer;

public 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));
		
		int n = Integer.parseInt(br.readLine());
		
		String arr = br.readLine();
		
		HashMap<Character,Integer> map = new HashMap<>();
		
		for(int i=0;i<26;i++) {
			map.put((char)(i+97),i+1);
		}
		
		long sum = 0;
		
		for(int i=0;i<n;i++) {
			char ch = arr.charAt(i);
			sum+=(map.get(ch)) * (Math.pow(31,i));
		}
		
		bw.write(sum+"");
		
		br.close();
		bw.close();
	}
}

50점을 맞은 코드에서는 Math.pow를 사용해서 계산을 했는데 찾아보니 Math.pow를 사용할 때 오차가 발생해서 그런 듯하다. (제 생각)

 

그래서 BigInteger라는 것을 사용했다.

BigInteger는 문자열이기 때문에 매우 큰 값에서도 사용 할  수 있다. 

 

BigInteger는 문자열이기 때문에 사칙연산이 안된다.

그래서 위의 코드와 같이 메소드를 이용해서 계산을 해주어야 한다.

 

메소드를메서드를 이용해서 계산을 할 때 계산순서에 유의해서 메서드를 이용해야 한다. 

괄호를 잘 사용해야 틀리지 않는다.