[백준 11659] JAVA 알고리즘 구간합구하기

[Java 알고리즘] 구간 합 구하기 (Prefix Sum) 예제

Java 알고리즘] 구간 합 구하기 (Prefix Sum) 예제

프로그래밍 문제를 풀다 보면 구간 합 (Prefix Sum)을 자주 만나게 됩니다.
특히 배열에서 특정 구간의 합을 빠르게 구해야 할 때, 단순 반복문으로 매번 계산하면 시간 초과가 나기 쉽습니다.
이럴 때 누적 합 배열을 사용하면 효율적으로 해결할 수 있습니다.

오늘은 Java로 구현한 구간 합 구하기 예제를 소개하겠습니다.

---

📌 문제 상황

• 첫 번째 줄: 수의 개수(suNo), 구간의 개수(quizNo)
• 두 번째 줄: 수열
• 이후 quizNo개의 줄: 합을 구하고자 하는 구간의 시작 인덱스와 끝 인덱스

👉 예를 들어,

 

5 3 5 4 3 2 1 1 3 2 4 1 5

이 입력이 들어오면,

• 1 ~ 3 구간 합 = 5+4+3 = 12
• 2 ~ 4 구간 합 = 4+3+2 = 9
• 1 ~ 5 구간 합 = 5+4+3+2+1 = 15
  이렇게 출력되어야 합니다.

---

📌 코드 구현

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

public class java002 {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader;
        StringTokenizer stringTokenizer;
        
        bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        int suNo, quizNo;
        suNo = Integer.parseInt(stringTokenizer.nextToken());
        quizNo = Integer.parseInt(stringTokenizer.nextToken());

        long S[] = new long[suNo + 1];
        
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        int i, j, q;
        
        i= 1;
        while(i<=suNo) {
            S[i] = S[i-1] + Integer.parseInt(stringTokenizer.nextToken());
            i++;
        }

        i = 0;
        j = 0;
        q = 0;
        while(q < quizNo) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            i = Integer.parseInt(stringTokenizer.nextToken());
            j = Integer.parseInt(stringTokenizer.nextToken());
            System.out.println(S[j] - S[i-1]);
            q++;
        }
    }
}

---

📌 코드 설명

1. 입력 받기
   • suNo: 수의 개수
   • quizNo: 구간 합을 구해야 할 횟수
2. 누적 합 배열 생성
   • S[i] = S[i-1] + 현재 값
   • 이렇게 하면 S[j] - S[i-1] 만으로 i ~ j 구간 합을 O(1) 시간에 구할 수 있음.
3. 구간 합 출력
   • 각 쿼리마다 시작점 i, 끝점 j를 입력받고
   • System.out.println(S[j] - S[i-1]); 로 결과 출력

---

📌 실행 결과

입력

5 3
5 4 3 2 1
1 3
2 4
1 5

 

 

출력

12
9
15

---

📌 관련 메서드 정리

1. BufferedReader

• BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
• 콘솔 입력을 빠르게 받기 위해 사용.
• readLine() : 한 줄을 문자열(String) 로 입력받음.

---

2. StringTokenizer

• StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
• 문자열을 구분자(delimiter) 기준으로 잘라 토큰 단위로 읽어옴.
• 자주 쓰는 메서드:
  • nextToken() : 다음 토큰(String) 반환
  • hasMoreTokens() : 아직 읽을 토큰이 남아 있는지 확인

---

3. Integer 클래스

• Integer.parseInt(String s) : 문자열을 정수(int)로 변환
• 예: "123" → 123

---

4. System 클래스

• System.out.println(value) : 출력 후 줄바꿈
• System.out.print(value) : 출력만 하고 줄바꿈 없음

---

5. 배열 관련

• long[] S = new long[suNo + 1];
• 누적 합 배열 생성
• 배열은 0부터 시작하지만, 구간합 계산의 편리함을 위해 +1 크기로 생성하여 S[0] = 0으로 초기화

---

📌 정리 표

클래스/메서드설명

BufferedReader.readLine()	한 줄 입력 받기
StringTokenizer.nextToken()	다음 토큰 반환
StringTokenizer.hasMoreTokens()	토큰 남아있는지 확인
Integer.parseInt(String)	문자열 → int 변환

📌 정리

• 단순 반복문으로 구간 합을 매번 구하면 O(N) 시간이 걸리지만,
• Prefix Sum(누적 합)을 사용하면 한 번의 사전 계산 이후 O(1)로 빠르게 구할 수 있습니다.
• 이는 코딩테스트에서 시간 초과 방지 필수 기법 중 하나이니 꼭 익혀두시면 좋습니다. 🚀