[Java/백준] 구간 합 구하기 #11659

문제

 

 

 

풀이

(1) 문제 분석하기

• 수의 개수 N과 합을 구해야 하는 횟수 M은 최대 100,000 임
  최악의 경우, 1억 회 이상 연산을 해야 하므로 1초 안에 계산을 끝낼 수 없음 → 구간 합 사용!

 

(2) 손으로 풀어보기

// 합 배열 공식
S[i] = S[i-1] + A[i]

// 구간 합 공식
S[j] - S[i-1]

1. N개의 수를 입력받으면서 바로 합 배열 생성
2. i부터 j까지 구간 합 공식으로 정답 출력
3. 배열의 index는 0부터, 합 배열의 index는 1부터 시작한다는 것에 주의하기!

 

(3) 슈도코드 작성하기

N(숫자의 개수), M(질의 개수) 저장하기
for(1부터 N 까지) {
	합 배열 생성하기(S[i] = S[i - 1] + A[i]
}
for(0부터 M 전까지) {
	질의 범위 받기(i ~ j)
	구간 합 출력하기(S[j] - S[i - 1])
}

 

(4) 코드 구현하기

💡 입력되는 데이터의 범위가 클 때는 Scanner 보다 BufferedReader를 사용하는 것이 효율적!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class PrefixSum11659 {
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        
		// 데이터의 범위를 고려하여 StringTokenizer 이용
		StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		int N = Integer.parseInt(stringTokenizer.nextToken());
		int M = Integer.parseInt(stringTokenizer.nextToken());
		
		long[]S = new long[N + 1];
		stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		for (int i = 1; i <= N; i++) { // 범위 주의!
			S[i] = S[i-1] + Integer.parseInt(stringTokenizer.nextToken());
		}
		for (int q = 0; q < M; q++) {
			stringTokenizer = new StringTokenizer(bufferedReader.readLine());
			int i = Integer.parseInt(stringTokenizer.nextToken());
			int j = Integer.parseInt(stringTokenizer.nextToken());
			System.out.println(S[j] - S[i-1]);
		}
		
	}
}

 

(번외) Sanner와 BufferedReader는 얼마나 차이 날까?

차례대로 BufferedReader, Scanner

• 실제로 Sanner와 BufferedReader로 문제를 풀어본 결과, 시간 차이가 있다는 걸 알 수 있음
• 항상 입력되는 데이터의 범위를 고려할 것!

 

 

 

 

11659번: 구간 합 구하기 4

 

※ 이 내용은 Do it! 알고리즘 코딩테스트 - 실전문제 풀이(JAVA) 강의를 듣고 정리한 내용입니다.