백준 11659 구간 합 구하기4 [JAVA]

Ga0·2024년 2월 15일

Java baekjoon 백준 자바

baekjoon

목록 보기

117/137

문제 해석

문제는 말그대로 주어진 구간에 해당하는 값들을 누적합 하는 문제이다.
첫번째 줄에는 수의 개수(N)와 합을 구해야하는 횟수(M)가 주어진다.
두번째 줄에는 수의 개수(N)만큼 숫자를 입력 받고, 세번째 줄부터는 수가 아닌 구간을 입력받아 해당되는 구간의 수를 누적합하면 되는 문제이다.
이 문제는 글로도 충분히 이해할 수 있기 때문에 그림 설명은 생략!!!

코드

틀린 코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static int[] number;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); //주어진 수의 개수(N)
        int M = Integer.parseInt(st.nextToken()); //누적합을 수행해야하는 횟수(M)

        number = new int[N+1]; // 인덱스는 0부터 시작하는데 구간은 1부터 시작하므로 N+1을 해줬다. (직관적으로 구할 수 있게)

        st = new StringTokenizer(br.readLine());

        for(int i = 1; i <= N; i++) { //누적합할 숫자 배열에 넣기
            number[i] = Integer.parseInt(st.nextToken());
        }

       while(M --> 0){
           st = new StringTokenizer(br.readLine());
           int i = Integer.parseInt(st.nextToken()); //i번째 부터
           int j = Integer.parseInt(st.nextToken()); //j번재 까지

            bw.write(prefixSum(i, j)+"\n");
        }

       br.close();
       bw.flush();
       bw.close();

    }

    //누적합 구하는 메소드
    public static int prefixSum(int start, int end){
        int sum = 0;

        for(int i = start; i <= end; i++){
            sum += number[i];
        }

        return sum;
    }
}

시간 초과가 나와서 틀린 코드이다...
보니 while(M --> 0) 안에 for문(prefixSum())이 있다. 즉, 반복문 안에 반복문이므로 시간초과가 나올 수 밖에 없는 구조...
다시 말해 O(NM) 시간이 걸리는...!!

    1 ≤ N ≤ 100,000
    1 ≤ M ≤ 100,000
    1 ≤ i ≤ j ≤ N

위는 M과 N의 범위값이고, 시간 제한은 1초이니 당연히 틀릴 수밖에 없는 코드이다.

맞은 코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static int[] number;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); //주어진 수의 개수(N)
        int M = Integer.parseInt(st.nextToken()); //누적합을 수행해야하는 횟수(M)

        number = new int[N+1]; // 인덱스는 0부터 시작하는데 구간은 1부터 시작하므로 N+1을 해줬다. (직관적으로 구할 수 있게)

        st = new StringTokenizer(br.readLine());

        number[0] = 0; //인덱스 0은 0으로 초기화
        for(int i = 0; i < N; i++) { //누적합할 숫자 배열에 넣기
            number[i+1] = number[i] + Integer.parseInt(st.nextToken()); //누적합을 해서 넣는 것이다.
        }

       while(M --> 0){
           st = new StringTokenizer(br.readLine());
           int i = Integer.parseInt(st.nextToken()); //i번째 부터
           int j = Integer.parseInt(st.nextToken()); //j번재 까지

            bw.write(number[j] - number[i - 1] + "\n"); //i번째는 i를 포함이므로 그 전의 값을 빼야하는 구조
        }

       br.close();
       bw.flush();
       bw.close();

    }

}

해결 방법은 배열을 저장했을 때부터 누적합해서 넣는 것이다.

만약 수가 5 4 3 2 1 이 있다고 가정하면 처음부터 배열을 저장할 때,
5 9 12 14 15 로 저장하는 것이다. 

만약 구간 1 3의 값을 구하고 싶다면 
3번째 인덱스인 12 - 1번째 인덱스까지 더하는 것이므로 1 - 1 = 0 인덱스를 빼면 된다. 
그럼 12가 나오게 되는 구조!