알고리즘 런타임 에러 - 잘못된 배열 인덱스 참조

동전 교환 문제를 풀다가, runtime Error 에 막혀서, 이번 기회에 정리해둔다. 

이 글은 백준 커뮤니티 글과 https://www.acmicpc.net/board/view/22980

아래 블로그를 참고했다. https://www.secmem.org/blog/2020/09/19/rte/ 

글 읽기 - 주로 런타임 에러가 발생하는 이유는 무엇인가요?

---

동전 교환 문제를 풀다가, runtime Error 에 직면했다. 

 

문제 출처 (자바 코딩 테스트 준비 김태원 강사님 강의) 

 

설명

다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가?

각 단위의 동전은 무한정 쓸 수 있다.

 

입력

첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종류가 주어지고,

그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.각 동전의 종류는 100원을 넘지 않는다.

 

출력

첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.

예시 입력 1 

3
1 2 5
15

예시 출력 1

3

 

힌트

출력 설명 : 5 5 5 동전 3개로 거슬러 줄 수 있다.

 

1차 시도 -> Runtime Error (IDE 에서는 정답 출력)  

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Coin {

    public int solution(int cnt, int[] opt, int target) {
        int[] ch = new int[target+1];
        int answer = 0;
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        ch[0] = 1;

        while(!q.isEmpty()) {
            int len = q.size();
            for(int i=0;i<len;i++) {
                int x = q.poll();
                for(int j=0;j<cnt;j++) {
                    int nx = x+opt[j];
                    if(ch[nx] == 0&&nx>=1&&nx<=target) {
                        q.offer(nx);
                        ch[nx] = 1;
                    }
                    if(nx == target) {
                        return answer + 1;
                    }
                }
            }
            answer++;
        }
        return 0;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Coin T = new Coin();
        int cnt = sc.nextInt();
        int[] opt = new int[cnt];
        for(int i=0;i<cnt;i++) {
            opt[i] = sc.nextInt();
        }
        int target = sc.nextInt();
        System.out.println(T.solution(cnt, opt, target));
    }
}

 

 

2차 시도 [정답] 

위의 코드에서는 입력값을 target+1 만큼만 주었다. 백준 커뮤니티 글을 보다보니, index를 입력값보다 작게 주면 runtime Error 가 날 수 있다고 해서, 입력값인 500+1만큼 주었더니, 정답이었다 ch[500] = 1 이 가능해야 하기 때문에, 501만큼 할당하면 0-500의 인덱스가 부여되기 때문이다.  

       int[] ch = new int[501]; //1 - 목표 금액(EX.1500) check 배열.
 //      int[] ch = new int[target+1];

---

 

인용한 블로그를 읽고, 런타임 에러를 다시 정리해보았다 (정리를 잘해주셔서 그냥 복사해왔는데, 꼭 전문을 읽어보길 추천한다) 

 

런타임 에러는 프로그램이 실행 도중 비정상적으로 종료되는 것이다.

이는 프로그램이 해서는 안 되는 행동을 했기 때문에 발생한다. 프로그램이 끝까지 정상적으로 실행되지 않았기에, 대부분의 온라인 저지에서는 출력 결과에 대한 채점 자체를 하지 않습니다. 설령 그 시점까지 출력한 내용이 있고 그것이 정답일지라도, 처음부터 끝까지 문제 없이 실행된 것이 아닌 이상 올바른 프로그램을 제출했다고 볼 수 없기 때문입니다.

잘못된 배열 인덱스 참조

가장 흔한 실수이며, 런타임 에러의 직접적인 원인으로서도 가장 빈번한 요소입니다. 말 그대로 배열의 크기를 넘어서는 인덱스를 통해 배열을 접근했을 때 발생합니다. 이것은 보다 일반화하면 잘못된 메모리 주소를 참조하는 경우에 해당하고, 아래 소개하는 많은 경우에도 직접적인 에러의 원인이 이에 해당합니다.

 

실수를 예방하기 위한 방법 

(1) 배열의 크기를 넉넉하게 잡기. 

예를 들어 입력이 10만 개 주어지는 문제라면 딱 int arr[100000];으로 쓰기보다는 int arr[100005];로 선언하는 것이 보다 안전합니다. 1, 2차원 배열에서 5칸의 여유분을 두는 것은 메모리 사용량이나 속도에 거의 아무런 영향이 없고, 그로 인해 가끔이라도 발생하는 실수를 방지할 수 있다면 훨씬 이득일 것입니다.

(2) 배열에 접근하기 위해 사용하는 인덱스가 배열의 범위를 벗어날 가능성이 있다면 범위를 먼저 검사하기. 대부분의 고수준 언어에서는 short-circuit evaluation을 사용하고 있기 때문에 && 연산자로 연결된 여러 조건문들의 순서만 알맞게 바꾸어주어도 문제를 방지할 수 있습니다. if (!visited[ny][nx] && 0 <= ny && ny < r && 0 <= nx && nx < c)로 쓰면 visited[ny][nx]를 먼저 접근하기 때문에 문제가 될 수 있지만, if (0 <= ny && ny < r && 0 <= nx && nx < c && !visited[ny][nx])로 쓰면 문제가 없게 됩니다.

(3) 배열을 선언할 때 그 크기가 충분한지 100% 확신이 들게 합시다. 

 

 

2를 고려해서 범위를 체크하는 조건문을 먼저 배치했다. 

                    if(nx>=1&&nx<=target&&ch[nx] == 0)
                  //if(ch[nx] == 0&&nx>=1&&nx<=target) {

3차 시도 - 정답 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    public int solution(int cnt, int[] opt, int target) {
//        int[] ch = new int[500]; //1 - 목표 금액(EX.1500) check 배열.
        int[] ch = new int[target+1];
        int answer = 0;
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        ch[0] = 1;

        while(!q.isEmpty()) {
            int len = q.size();
            for(int i=0;i<len;i++) {
                int x = q.poll();
                for(int j=0;j<cnt;j++) {
                    int nx = x+opt[j];
                    if(nx>=1&&nx<=target&&ch[nx] == 0) {
                        q.offer(nx);
                        ch[nx] = 1;
                    }
                    if(nx == target) {
                        return answer + 1;
                    }
                }
            }
            answer++;
        }
        return 0;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Main T = new Main();
        int cnt = sc.nextInt();
        int[] opt = new int[cnt];
        for(int i=0;i<cnt;i++) {
            opt[i] = sc.nextInt();
        }
        int target = sc.nextInt();
        System.out.println(T.solution(cnt, opt, target));
    }
}