https://www.acmicpc.net/problem/16953
🚩NumberFormat
오늘은 백준 16953번을 BFS을 이용해서 Java로 풀어봤습니다. 생각보다 간단한 문제라고 생각이 들었고 몇 분 만에 구현할 수 있었습니다. 하지만 계속 백준에서 런타임 에러(NumberFormat) 결과를 받았습니다. Intelli J에서는 예제를 전부 통과했는데 말이죠..
NumberFormat이 발생하는 이유는 주로 2가지가 있다고 합니다.
- 문자열 형식 오류 : 변환하려는 문자열에 숫자가 아닌 문자가 포함된 경우입니다. 예를 들어, "123a" 같은 문자열은 숫자가 아니므로 변환할 수 없습니다.
- 숫자 범위 초과 : Integer.parseInt나 Long.parseLong은 각각 int와 long의 범위를 초과하는 값을 처리할 수 없습니다. 예를 들어, Integer.parseInt("2147483648")와 같이 int의 최댓값을 넘는 값을 변환하려고 하면 NumberFormatException이 발생합니다.
NumberFormatException에 대해 알아본 후, 저는 숫자 범위 초과가 의심하게 되어, 코드에서 어떤 부분에서 int 범위를 넘는 값이 발생하는지 찾아보았습니다.
음,,주어진 입력값의 범위는 분명 20억이 넘지 않는데..
계속 고민하다가 결국 다른 분들의 풀이를 참고하여 숫자 범위 초과 때문이었고 int형 대신 long으로 바꿔야 통과가 된다는 것을 알 수 있었습니다.
🤔 왜 long을 써야 하는걸까..?
만약 3억을 10억으로 만들 경우에는, 두 가지 종류의 연산 중 마지막 자리에 1을 붙이는 연산을 진행할 경우에 Queue에 30억+1이 들어가야 하므로 overflow가 발생됩니다!!
그래서 int가 아닌 long을 사용해야 했습니다.
아래는 제출한 코드입니다.
import java.io.*;
import java.util.*;
class Node {
long num;
int depth;
public Node(long num, int depth) {
this.num = num;
this.depth = depth;
}
}
public class Main {
static long B;
static int answer;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
B = Integer.parseInt(st.nextToken());
answer = Integer.MAX_VALUE;
bfs(A, 0);
if (answer == Integer.MAX_VALUE) {
bw.write(-1 + "");
} else {
answer += 1;
bw.write(answer + "");
}
bw.close();
}
public static void bfs(int a, int b) {
Queue<Node> queue = new LinkedList<>();
queue.add(new Node(a, b));
while (!queue.isEmpty()) {
Node now = queue.poll();
long num = now.num;
int depth = now.depth;
if (num == B) {
answer = Math.min(answer, depth);
return;
}
if (num > B) continue;
queue.add(new Node(num * 2, depth + 1));
String str = String.valueOf(num);
str += "1";
long strNum = Long.parseLong(str);
queue.add(new Node(strNum, depth + 1));
}
}
}
'Algorithm' 카테고리의 다른 글
[백준] 16139 : 인간-컴퓨터 상호작용 (JAVA) (0) | 2024.12.02 |
---|---|
[백준] 10816 : 숫자 카드 2 (JAVA) (0) | 2024.11.18 |
[백준] 1916 : 최소비용 구하기 (JAVA) (2) | 2024.11.13 |
[백준] 11054 : 가장 긴 바이토닉 부분 수열 (JAVA) (1) | 2024.11.08 |
[백준] 13549 : 숨바꼭질 3 (JAVA) (0) | 2024.11.05 |