[Java] 자바 구간합 구하는 방법 알아보기

2023-03-24

---

사진: Unsplash 의 Anita Austvika

---

1. 방법

 

우선 주어진 배열과 동일한 크기의 배열을 생성해 준다. 해당 주어진 배열을 1회 순회하며, 새로운 배열(sumArr)에 sumArr [i-1] + arr [i] 공식으로 대입해 주면 된다. 

 

이후에 주어진 구간합을 구할때는 구간 끝 - 구간시작-1 공식을 이용하면 기존 배열을 다시 반복 순회하지 않아도 답을 도출할 수 있다.

 

    static int [] sumArr;
    @Test
    public void test(){
        int [] arr = new int [] {4,5,13,43,22,1,5,7,8};
        sumArr = new int [arr.length];
        sumArr[0] = arr[0];//구간합 첫번째 인자 셋팅

        //구간합 구하기
        for(int i = 1; i < arr.length; i++){
            sumArr[i] = sumArr[i-1] + arr[i];
        }

        //배열 3 ~ 5의 구간합은?
        int start = 3;
        int end = 5;

        //구간합 공식 사용
        System.out.println(sumArr[end] - sumArr[start-1]);
        //구간합 메소드 사용
        System.out.println(distanceSum(end,start));

        //실제 루프 사용
        int sum = 0;
        for(int i = start; i <= end; i++){
            sum += arr[i];
        }
        System.out.println(sum);

    }

    public int distanceSum(int end, int start){
        return sumArr[end] - sumArr[start-1];
    }

---

메인 이미지 출처 : 사진: Unsplash의Anita Austvika