글 읽기 - ArrayIndexOutOfBound의 원인 및 Test Case를 알고싶습니다.

testjyl 2년 전 0

안녕하세요, 작성한 코드에서 스스로 문제점을 해결하지 못해 질문드립니다.

범위를 변경하여 정답을 받았지만 아래 처럼 코드를 작성하는 경우 ArrayIndexOutOfBound가 발생하는 이유를 모르겠습니다.

23번째 에러로 보여지는데 if(nodes[i] >= 0 && nodes[i] <= Math.max(N, K) + 10 && cost[nodes[i]] == 0)

이렇게는 왜 에러가 발생하는지 원인을 찾고 싶습니다.

제가 의도한 풀이는 100000까지의 연산을 수행하지 않고 단순히 범위를 좁히고 싶은 의도로 작성했는데 원인을 모르겠습니다.

소중한 의견 부탁드립니다.

감사합니다.

import java.util.*;

public class Main {

    private static int[] cost = new int[100001];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int K = scanner.nextInt();

        Queue<Integer> needVisitQueue = new LinkedList<>();
        needVisitQueue.add(N);

        while (!needVisitQueue.isEmpty()) {
            int current = needVisitQueue.remove();
            if(current == K) {
                System.out.println(cost[current]);
                return;
            }
            int[] nodes = {current+1, current-1, current*2};
            for (int i = 0; i < nodes.length; i++) {
                if(nodes[i] >= 0 && nodes[i] <= Math.max(N, K) + 10 && cost[nodes[i]] == 0) {
                   cost[nodes[i]] = cost[current] + 1;
                    needVisitQueue.add(nodes[i]);
                }
            }
        }
    }

}

djm03178 2년 전 0

Math.max(N, K) + 10는 cost의 크기인 10만 1을 넘어갈 수 있습니다.

그리고 일반적으로는 이렇게 각 케이스에 맞게 범위를 좁히려고 노력하지 않는 편이 오히려 더 빠릅니다. 시간은 전체 케이스에서 가장 오래 걸린 것만이 중요하고, 그런 케이스는 대체로 가장 큰 데이터에서 만들어지므로 어차피 10만까지의 인덱스를 다 써야할 것이기 때문입니다. 그런 케이스에서 범위가 딱 10만으로 정해져있는 것이 매번 max(n, k) + 10을 계산하는 것보다 빠르므로 최악의 경우에서더 이득이 되고, 최악의 경우가 곧 최종 시간이므로 전체에서도 더 이득이 됩니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

ArrayIndexOutOfBound의 원인 및 Test Case를 알고싶습니다.

testjyl 2년 전 0

djm03178 2년 전 0

djm03178 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말