[백준 - JAVA] Hashing

15829번: Hashing (acmicpc.net)

15829번: Hashing

50점

 

100점 실패

성공

http://boj.kr/0f99738217d84c81be87df3ddb708149

공유 소스 보기

import java.util.Scanner;

class Main{
    
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
		
		long result = 0,
            trash = sc.nextInt();

		String str = sc.next();
		
		char[] arr = str.toCharArray();
		
		for(int i = arr.length - 1; i > -1; i--) {
            
			result += ((int) arr[i] - 96);
			if(i == 0) break;
			result *= 31;
            if(result > 1234567891) result %= 1234567891;	

		}
        
		System.out.println((int)result);
        
    }    
    
}

해싱 문제다.. 해싱에 관해서는 문제 설명에 다 쓰여있다.

 

처음에 그냥 막힘 없이 풀면서 음.. 값 초과하려나? 하고

 

제출했는데 처음 보는 50점이 나왔다

 

???????????

 

문제 다시 보니까 값의 범위에 따라 점수가 다르게 나오는 걸 확인

 

나중에 풀어야 지하고 오늘 풀었다.

 

풀이 전개 방식은

 

ex. 1 × 31^0 + 2 × 31^1 + 3 × 31^2 + 4 × 31^3 + 5 × 31^4

 

얘를 역으로 뒤에서부터 연산하게 했다.

 

5에 31 곱하고

 

4 더하고 31을 곱하면

 

5*31과 4를 쪼개서

 

각각 31을 곱하는 것과 동일하니

 

이렇게 하면 될 거 같았다.

 

double로 바꿔서 풀었는데 자꾸 틀렸습니다 나오는 걸 보고

 

음.. 전에 부동소수점인가 뭐라 들었던 거 같은데 하면서

 

소수가 없는데 왜 그럴까 고민하고 있었다.

 

근데 잘 보니까 1.~~~e71 이런 식으로 출력되는 걸 보고

 

저럼 안되는갑다 싶어서 자료형에 대해 다시 읽어보고

 

long으로 제출했다. 통과