글 읽기 - [세그먼트 트리] Array Index Out Of Bounds 에러가 발생해요

xhdtn8070 3년 전 0

https://www.acmicpc.net/source...

세그먼트 트리를 공부한 후에 짜본 코드입니다.

예제는 통과했지만, 제출 중 런타임 에러 (ArrayIndexOutOfBounds)가 발생했는데,

어떤 상황에서 런타임 에러가 발생하는지 예상이 안되어 질문올립니다.

감사합니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int N;
    static int arr[];
    static int tree[];
    static int index[];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        index = new int[N];
        tree = new int[N*2];
//        Arrays.fill(arr,1);
        //해당 숫자가 어느 인덱스를 가지고 있는지를 저장함
        for(int i = 0; i < N; i++){
            int k = Integer.parseInt(br.readLine());
//            arr[i]=k;
            arr[i]=1;
            index[k-1] = i;
        }

        init(0,N-1,1);


        int k;
        boolean flag = true;

        for(int i = 0; i < N; i++){
            if(flag){
                k = i/2;
                System.out.println(sum(0,N-1,1,0,index[k])-1);
            }else{
                k = N-1-i/2;
                System.out.println(sum(0,N-1,1,index[k],N-1)-1);
            }
            update(0, N-1, 1, index[k],-1);
            flag = !flag;
        }

    }
    //1부터 N까지
    //
    private static int init(int start, int end, int node) {
        if(start==end) return tree[node] = arr[start];
        int mid = (start+end)/2;
        return tree[node] = init(start,mid,node*2) + init(mid+1, end, node*2+1);
    }
    // start: 시작 인덱스, end: 끝 인덱스
    // left, right : 구간 합을 구하고자 하는 범위
    private static int sum(int start, int end, int node, int left, int right){
        if(left>end || right < start) return 0;
        if(left <= start && end <= right) return tree[node];
        int mid = (start + end) /2;
        return sum(start, mid, node *2, left,right) + sum(mid +1, end, node *2 +1, left, right);
    }
    // start: 시작 인덱스, end: 끝 인덱스
    // index : 구간 합을 수정하고자 하는 노드
    // dif : 수정할 값
    private static void update(int start, int end, int node, int index, int dif){
        if(index < start || index > end) return;
        tree[node] += dif;
        if(start==end) return;
        int mid = (start + end) /2;
        update(start, mid, node * 2, index, dif);
        update(mid+1,end, node *2 +1, index, dif);
    }
}

문제

문제

출처

ICPC

[세그먼트 트리] Array Index Out Of Bounds 에러가 발생해요

xhdtn8070 3년 전 0

luniro 3년 전 1

xhdtn8070 3년 전 0

luniro 님 매우 감사드립니다.

제가 기본기가 부족함을 한번 더 느끼게 되었습니다.

감사합니다.

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말