[백준] 구간 합 4

문제

시간 제한 : 1 초

문제 :
수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력 :
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다.
둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다.
셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력 :
총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

예시입력 :
5 3
5 4 3 2 1
1 3
2 4
5 5

예시 출력 :
12
9
1

제한 범위 :
1 ≤ N ≤ 100,000
1 ≤ M ≤ 100,000
1 ≤ i ≤ j ≤ N

 

 

제한 범위는  N과 M이 100000이하 이므로, 최악의 경우 모든 배열의 원소 n개의 합을 m번 구하게 된다면,

100000 x 100000 으로 최대 약 100억번의 연산을 하게 된다.

 

따라서 시간 초과가 발생 할 것이기 때문에 

 

구간합 알고리즘으로 배열의 합을 구하는 연산을 O(1) 의 시간 복잡도로 개선 해야 한다.

 

 

해답

class Solution {
    public void solve() throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] str = bf.readLine().split(" ");
        int length = Integer.parseInt(str[0]);
        int count = Integer.parseInt(str[1]);

        int[] intArray = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] intSumArray = new int[length];

        // 누적 합 배열 생성
        for (int i = 0; i < length; i++) {
            if (i == 0) {
                intSumArray[i] = intArray[i];
            } else {
                intSumArray[i] = intSumArray[i - 1] + intArray[i];
            }
        }

        // 구간 합 계산
        for (int i = 0; i < count; i++) {
            int[] numArr = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int start = numArr[0];
            int end = numArr[1];

            int prefixSum;
            if (start == 1) {
                prefixSum = intSumArray[end - 1];
            } else {
                prefixSum = intSumArray[end - 1] - intSumArray[start - 2];
            }

            bw.write(String.valueOf(prefixSum));
            bw.newLine();
        }
        bw.flush();
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        Solution s = new Solution();
        s.solve();
    }
}

과정 설명

1.  배열의 길이, 구해야 할 구간합의 수 저장

String[] str = bf.readLine().split(" "); 

int length = Integer.parseInt(str[0]); 
int count = Integer.parseInt(str[1]);

우선 입력의  첫째 줄에 배열의 길이와, 구해야 할 구간 합의 수가 주어진다.

이를 String형 배열에 저장하고. 각 인덱스에 해당하는 값인

length ( 배열의 길이 ) 와 count ( 구해야 할 구간 합의 수 ) 에 저장했다.

 

 

 

2. 입력의 둘째 줄에 주어진 배열을 BufferedReader로 읽어들인 후 int형 배열로 저장한다.

int[] intArray = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

초기에 주어지는 배열은 불변이므로 배열 형태로 저장하였다

 

 

 

3.  합배열을 저장하기 위한 배열 선언

ArrayList<Integer> intSumArray = new ArrayList<>(); 

->

int [] intSumArray = new int[length];

앞서 말했듯 합배열을 통해 구간합을 구하는 연산을 O(1) 으로 할수 있다.

초기에 ArrayList로 크기를 초기화 하지 않고 합배열을 구했는데, length로 배열 길이가 정해지고, 중간에 값을 삽입하거나 삭제할 일이 없기 때문에  int형 배열에 length 변수의 크기를 배열 크기로 지정하는 방식이 더 효율적인 것 같다.

 

 

 

 

4.  합 배열을 계산하여 삽입. 

 for (int i = 0; i < length; i++) {
            if (i == 0) {
                intSumArray[i] = intArray[i];
            } else {
                intSumArray[i] = intSumArray[i - 1] + intArray[i];
            }
        }

배열의 길이만큼 초기에 intSumArray의 크기를 지정했기 때문에 메모리를 재 할당하지 않는다.

 

 

 

5. 구해야 하는 구간합의 개수만큼 반복하여 구간합 구하기

for (int i = 0; i < count; i++) {
            int[] numArr = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int start = numArr[0];
            int end = numArr[1];

            int prefixSum;
            if (start == 1) {
                prefixSum = intSumArray[end - 1];
            } else {
                prefixSum = intSumArray[end - 1] - intSumArray[start - 2];
            }

            bw.write(String.valueOf(prefixSum));
            bw.newLine();
        }

BufferedReader로 반복 마다 구간합에 대한 정보를 읽어들이고 구간의 시작과 끝 자리를 저장한다. start와 end 변수에 저장.

구간합은 S[i,j] = S[j] - S[i-1] 이고,  index는 0부터 시작한다는 점을 고려하여

intSumArray[end - 1] - intSumArray[start - 2] 로 구간합을 구한다.

 

다만 놓쳤던 부분이 첫째 자리부터 구간합을 구할 때,

저 식대로라면  intSumArray[start - 2] 에서 index가 -1 이 되어버리기 때문에 ArrayIndexOutOfBoundsException 이 발생한다.

 

항상 edgecase를 고려하면서 코드를 짰어야 했지만 이 부분을 잠시 놓쳤던 것 같다.

 

또한 bw.write에 prefixSum을 그대로 넣었을때 출력 결과가 깨져서 나왔다.

출력 결과

그 이유는 BufferedWriter는 문자열 형태만 출력할 수 있기 때문이었다.

 

다만 헷갈렸던 이유는

write 함수가 int형 파라미터를 받을 수 있기 때문이었다.

 

그러나 int형 파라미터는 ascii 코드를 받아 그에 해당하는 문자를 출력하는 것이기 때문에 문제가 생겼던 것이었다.

 

 

단순히 파라미터만 보고 메서드를 추측할 것이 아니라, 어디에 무엇을 목적으로 쓰이는 것일지를 생각하면서 코딩해야겠다.