1789 문제를 풀고 있었다.
문제 링크
지금까지 알고리즘 풀 때는 입력을 받아서(BufferedReader) 이를 숫자로 바꿀 때는 Integer.parseInt를 통해서 아무 생각없이 int형으로 변환했다.
int 사용 -> NumberFormat 에러 발생
아래는 내가 해당 문제를 풀 때 쓴 코드이다.
중요한 것은 내가 숫자는 무조건 int형을 사용했다는 것이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Backjoon_1789 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int S = Integer.parseInt(br.readLine());
sb.append(find(S, 1));
System.out.println(sb);
}
private static int find(int S, int total) {
int n = 1;
while (true) {
if (total < S) {
n++;
total += n;
continue;
}
if (total == S) {
return n;
}
if (total > S) {
return n - 1;
}
}
}
}그러나... NumberFormat 에러가 발생했다.
이 에러를 보고 든 생각은
어????? 입력 받은 String을 Int형으로 잘 변환하지 못 하고 있다는 건데?라는 생각이 들었고
하지만 내 코드에서는 그런 상황을 찾아볼 수가 없었다.
NumberFormat 이 발생하는 상황에 대해 잘 설명되어 있는 글
이 글을 보고 내 상황에는 어떤 걸 적용해야 할까? 라고 고민을 하게 되었다.
그 결과 나는 이 상황에 해당된다는 생각이 들었다.
그래서 아... Integer의 범위에 벗어날 수가 있다고?
엄청 큰 수를 다룰 때는 BigInteger을 다루라고? 그럼 BigInteger로 바꾸자!!!
그럼 해결되겠지?ㅋ
라는 생각으로 BigInteger로 코드를 변경해주었다.
Integer, Long, BigInteger의 범위
| int | long | |
|---|---|---|
| 저장 공간 | 4byte | 8byte |
| 범위 | 2147483648 ~ 2147483647 | -9223372036854775808 ~ 9223372036854775807 |
long보다 범위가 큰 경우에는 BigInteger을 사용한다.
문제를 다시 봐보자
문제에서는 자연수 S(1 ≤ S ≤ 4,294,967,295) 가 주어진다고 했다.
따라서 int형을 사용했을 때는 범위를 넘어갈 수 있기 때문에 NumberFormat에러가 발생함을 알 수 있다.
그렇기 때문에 int형보다 큰 Long이나 BigInteger을 사용하면 되는 것이다.
BigInteger 사용 -> 틀렸습니다.
public class Backjoon_1789 {
public static void main(String[] args) throws IOException {
/**
코드 생략
*/
BigInteger S = BigInteger.valueOf(Long.parseLong(br.readLine()));
sb.append(find(S, 1));
/**
코드 생략
*/
}
private static int find(BigInteger S, BigInteger total) {
/**
코드 생략
*/
}
}이제 통과하겠지? 라고 생각하고 있었는데
틀렸다고 한다...
이유는 다음과 같았다.
BigInteger a = BigInteger.ONE;
a.add(BigInteger.ONE);을 하면 a가 2가 되길 기대했지만 실제로는 a의 값은 변하지 않는다.
왜냐하면 a.add()를 하면 새로운 BigInteger 객체를 생성하는 것이기 때문이다.
BigInteger b = a.add(BigInteger.ONE);따라서 내 상황에서는 BigInteger를 사용하는 게 맞지 않다.
또한 long 타입의 범위 내이기 때문에 long타입을 사용하기로 했다.
long 타입 사용 -> 시간 초과
이번엔 시간 초과가 났다....ㅋ
public class Backjoon_1789 {
public static void main(String[] args) throws IOException {
/**
코드 생략
*/
long S = Long.parseLong(br.readLine());
/**
코드 생략
*/
}
private static int find(long S, int total) {
/**
코드 생략
*/
}
}생각을 해보니 total은 결국 S를 넘거나 같아야 한다.
그러면 total도 long범위를 넘을 수 있다는 것이다.
따라서 이때 overflow가 발생할 수 있다.
오버플로우가 발생하면 왜 시간초과가 날까?
Copy code
public class OverflowExample {
public static void main(String[] args) {
int maxValue = Integer.MAX_VALUE; // 2,147,483,647
System.out.println("Max Value: " + maxValue);
// 오버플로우 발생
int overflowValue = maxValue + 1;
System.out.println("Overflow Value: " + overflowValue);
}
}maxValue는 int형의 최대값을 가지고 있었다.
하지만 여기에 +1을 하게 되면 예상치 못한 값을 얻을 수 있다.(오버플로우 발생)
Max Value: 2147483647
Overflow Value: -2147483648따라서 이 경우에 S보다 total이 크거나 같은 값을 값게 할 수 없게 되고 그 결과 시간초과가 발생한다.
제대로 된 long 타입 사용 -> 맞았습니다
큰 값을 다룰 때 적절한 데이터 타입을 사용했더니
1. NumberFormat 에러 발생도 하지 않았고
2. OverFlow 도 발생하지 않았다.
public class Backjoon_1789 {
public static void main(String[] args) throws IOException {
/**
코드 생략
*/
long S = Long.parseLong(br.readLine());
/**
코드 생략
*/
}
private static int find(long S, long total) {
/**
코드 생략
*/
}
}교훈
숫자는 int! 가 무조건 인 것은 아니다.
문제에서 주어진 범위를 보고 그 범위에 맞는 적절한 타입을 선택하자.
