[Java] 자바 알고리즘 풀 때 int vs long 언제 써야할까?

알고리즘 문제 풀다가 자바에서는 종종 int 를 쓰면 값이 이상하게 나오는 경우가 많다.

파이썬은 숫자 범위 제한이 없어서 그냥 막 써도 괜찮은데, 자바는 자료형에 따라 범위가 정해져 있어서 조심해야함

---

✔️ 기본 정수 자료형 범위

자료형	범위
int	약 ±21억
long	약 ±900경

---

✔️ 자료형 선택 기준

1. 입력값의 최대 범위 확인하기
   
   • 배열 크기, 원소 값, 반복 횟수 등 다 확인
   • 단순히 값이 작아 보여도, 곱하거나 누적될 경우 주의
2. 곱셈, 누적합 등 중간 결과가 커지는 경우
   
   • ex) 1_000_000 * 1_000_000 → 10^12 (int 넘음)
   • 이럴 땐 반드시 long 사용
3. 지수 연산이 있는 경우
   
   • 문제에서 "행렬 제곱", "A^B" 같이 나오는 경우
   • 반복적인 곱셈이 발생해서 수가 커질 수 있음

---

✔️ 자주 하는 실수

int a = 1_000_000;
int b = 1_000_000;

long result = a * b; // ❌ int 범위 넘고 나서 long에 저장됨 → 잘못된 값

long result = (long) a * b; // ✅ 앞에 형변환 하나만 해도 됨

---

✔️ 예시: 백준 10830번 행렬 제곱

- 행렬 원소: 최대 1,000
- 지수 B: 최대 10^11

→ 반복 곱셈이 많고 중간 값이 커짐
→ 무조건 long 써야 함

---

✔️ 체크 리스트

[ ] 배열/값의 범위 확인했나?
[ ] 곱셈이나 누적합 연산 있는가?
[ ] 결과가 2억 넘을 가능성 있음?
[ ] long이 필요한 계산에 (long) 캐스팅 해줬나?