728x90
❓ Hashing
🏷️ 관련 주제 : 자료형
💦 나의 시도
Try01. int형과 BufferedReader의 read() 메서드를 이용한 시도
- 문자열 길이
L, 거듭제곱해주는 숫자r, moduler NumberM을 int형 변수로 선언- r = 31
- M = 1234567891
- 0 ~ (L - 1) 범위를 반복문을 돌면서 알파벳을 한 글자씩 읽기
BufferedReader의read()메서드를 사용하여 알파벳을 정수로 읽은 값에 ('a' - 1) 값을 뺀 값을 int형 변수에 할당
(이렇게 하면 알파벳 'a' 값을 1, 'b'는 2, ...로 바꿀 수 있음)- 0 ~ (i - 1) 범위를 반복문을 돌면서 a에 r을 곱함.
- 만약 a가 M보다 크면 a를 M으로 나눈 나머지를 a에 할당
- 반복문이 끝나면 H에 a를 더해줌
- 반복문이 끝나면 H를 출력
💥 50점(Small 문제만 맞았습니다.)
문제에 두가지 유형의 테스트 케이스가 있는데
첫번째 Small 문제는 1 ≤ L ≤ 5 범위에서 문제를 해결하는 것이고
두번째 Large 문제는 1 ≤ L ≤ 50 범위에서 문제를 해결해야하는데
Large문제에서 틀림
- 변수의 범위가 달라지는 것이므로 자료형의 문제일 것 같아서 int형을 long형으로 바꿔봄.
Try02. 결과값으로 반환하는 H 변수를 long형으로 변경
💥 50점(Small 문제만 맞았습니다.)
Try03. 반복문에서 $r^i$을 매번 새롭게 구하던 것을 int R을 반복문 밖에서 선언하여 시도
💥 50점(Small 문제만 맞았습니다.)
이전 코드
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());
int r = 31;
int M = 1234567891;
long H = 0L;
for (int i = 0; i < L; i++) {
int a = br.read() - 'a' + 1;
for (int j = 0; j < i; j++) {
a *= r;
if (a > M) {
a %= M;
}
}
H += a;
}
System.out.println(H);
}
}바꾼 코드
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());
int r = 31;
int M = 1234567891;
int R = 1;
Long H = 0L;
for (int i = 0; i < L; i++) {
int a = br.read() - 'a' + 1;
a = a * R % M;
H = (H + a) % M;
R = R * r % M;
}
System.out.println(H);
}
}Try04. 거듭제곱과 관련된 모든 변수를 long으로 선언
R : r을 거듭제곱한 값($r^i$)
a : 입력한 문자열에서 읽어 온 알파벳을 정수로 변환한 값
H : 결과값으로 출력할 변수
맞았습니다!!
- 메모리 : 14220 KB
- 시간 : 108 ms
- 코드 길이 : 636 B
Large문제가 범위만 달라서 깊게 생각하지 않고 어림짐작으로 r을 거듭제곱하는 부분에서 자료형의 범위를 초과할 것 같아서 변수형만 바꿔서 문제를 맞혔는데
아무래도 변수 L의 범위에 따라 값들이 어떻게 바뀌는지 깊게 생각해 보는 것이 더 좋겠지?
라는 생각이 들어서 값의 범위를 생각해 보았다.
System.out.println("int형 최댓값:"+Integer.MAX_VALUE+", long형 최댓값:"+Long.MAX_VALUE);
long maxR = 1234567890L * 31;
System.out.println("maxR:"+maxR+", int형 최댓값 초과:" + (maxR > Integer.MAX_VALUE) + ", long형 최댓값 초과:"+(maxR > Long.MAX_VALUE));
long maxA = 26L * 1234567890;
System.out.println("maxA:"+maxA+", int형 최댓값 초과:" + (maxA > Integer.MAX_VALUE) + ", long형 최댓값 초과:"+(maxA > Long.MAX_VALUE));
long maxH = 1234567890L + 1234567890;
System.out.println("maxH:"+maxH+", int형 최댓값 초과:" + (maxH > Integer.MAX_VALUE) + ", long형 최댓값 초과:"+(maxH > Long.MAX_VALUE));
(출력 결과)
int형 최댓값:2147483647, long형 최댓값:9223372036854775807
maxR:38271604590, int형 최댓값 초과:true, long형 최댓값 초과:false
maxA:32098765140, int형 최댓값 초과:true, long형 최댓값 초과:false
maxH:2469135780, int형 최댓값 초과:true, long형 최댓값 초과:false
즉, R과 a와 H는 int형 범위를 초과하는 경우가 생길 수 있으므로 long형으로 선언해야 문제를 맞힐 수 있다!
R : r의 거듭제곱
a : 알파벳 소문자 a ~ z를 1 ~ 26으로 변환한 정수
H : 해쉬 함수 결과값
📑제출 기록 및 오답 원인
💯 해결 방법
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());
int r = 31;
int M = 1234567891;
long R = 1L;
long H = 0L;
for (int i = 0; i < L; i++) {
long a = br.read() - 'a' + 1;
a = (a * R) % M;
H = (H + a) % M;
R = (R * r) % M;
}
System.out.println(H);
}
}
ℹ️ 자바 기본 자료형 크기 및 범위
자바 기본 자료형 크기 및 범위 구하는 코드
import java.text.DecimalFormat;
public class Test {
public static void main(String[] args) {
DecimalFormat formatter = new DecimalFormat("###,###.###");
System.out.println("\n[정수 자료형]\n");
System.out.println("1. byte");
System.out.println("- 크기: " + Byte.BYTES + "바이트");
System.out.println("- 최솟값: " + formatter.format(Byte.MIN_VALUE));
System.out.println("- 최댓값: " + formatter.format(Byte.MAX_VALUE));
System.out.println("---------------------------");
System.out.println("2. short");
System.out.println("- 크기: " + Short.BYTES + "바이트");
System.out.println("- 최솟값: " + formatter.format(Short.MIN_VALUE));
System.out.println("- 최댓값: " + formatter.format(Short.MAX_VALUE));
System.out.println("---------------------------");
System.out.println("3. int");
System.out.println("- 크기: " + Integer.BYTES + "바이트");
System.out.println("- 최솟값: " + formatter.format(Integer.MIN_VALUE));
System.out.println("- 최댓값: " + formatter.format(Integer.MAX_VALUE));
System.out.println("---------------------------");
System.out.println("4. long");
System.out.println("- 크기: " + Long.BYTES + "바이트");
System.out.println("- 최솟값: " + formatter.format(Long.MIN_VALUE));
System.out.println("- 최댓값: " + formatter.format(Long.MAX_VALUE));
System.out.println("---------------------------");
System.out.println("\n[실수 자료형]\n");
System.out.println("5. float");
System.out.println("- 크기: " + Float.BYTES + "바이트");
System.out.println("- 최솟값: " + Float.MIN_VALUE);
System.out.println("- 최댓값: " + Float.MAX_VALUE);
System.out.println("---------------------------");
System.out.println("6. double");
System.out.println("- 크기: " + Double.BYTES + "바이트");
System.out.println("- 최솟값: " + Double.MIN_VALUE);
System.out.println("- 최댓값: " + Double.MAX_VALUE);
System.out.println("---------------------------");
System.out.println("\n[문자 자료형]\n");
System.out.println("7. char");
System.out.println("- 크기: " + Character.BYTES + "바이트");
System.out.println("- 최솟값: " + formatter.format((int) Character.MIN_VALUE));
System.out.println("- 최댓값: " + formatter.format((int) Character.MAX_VALUE));
}
}
(출력 결과)
[정수 자료형]
1. byte
- 크기: 1바이트
- 최솟값: -128
- 최댓값: 127
---------------------------
2. short
- 크기: 2바이트
- 최솟값: -32,768
- 최댓값: 32,767
---------------------------
3. int
- 크기: 4바이트
- 최솟값: -2,147,483,648
- 최댓값: 2,147,483,647
---------------------------
4. long
- 크기: 8바이트
- 최솟값: -9,223,372,036,854,775,808
- 최댓값: 9,223,372,036,854,775,807
---------------------------
[실수 자료형]
5. float
- 크기: 4바이트
- 최솟값: 1.4E-45
- 최댓값: 3.4028235E38
---------------------------
6. double
- 크기: 8바이트
- 최솟값: 4.9E-324
- 최댓값: 1.7976931348623157E308
---------------------------
[문자 자료형]
7. char
- 크기: 2바이트
- 최솟값: 0
- 최댓값: 65,535🏷️ 문제 풀면서 참고한 블로그
728x90
