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

 

✅ 핵심 풀이

수의 개수와 구해야 하는 횟수가 둘 다 10만 이므로

만약 문제에서 주어지는 데이터가 n과 m모두 10만인 최대치로 주어진다면

구해야하는 횟수 x 수의 범위 => 100억으로, 시간 제한인 1초(약1억)를 넘어가게 된다.

 

따라서 해당 문제는 a부터 b까지의 범위에 대한 합 정보, 다시 말해 구간 합의 정보를

미리 저장해두고 i번째와 j번째 수의 합을 출력해야 시간초과를 하지 않게 된다.

 

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		int[] sum = new int[n+1];
		
		st = new StringTokenizer(br.readLine());
		sum[0] = 0;
		for(int i = 1; i<=n; i++) {
			sum[i] = sum[i-1] + Integer.parseInt(st.nextToken());
		}
		
		for(int i = 0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			sb.append(sum[b] - sum[a-1]).append("\n");
		}
		
		System.out.println(sb);
	}

}

 

a부터 b까지의 합을 알고 싶다면 (a<=b)

sum[b] - sum[a-1]을 해주면 된다.

예를 들어 2부터 5까지의 합이라면

sum[5] = num[1]+num[2] + num[3] + num[4] + num[5] 이고

sum[2-1] = sum[1] = num[1] 이므로

sum[5] - sum[1] = num[2] + num[3] + num[4] + num[5] 로

2부터 5까지의 합을 알 수 있다.

 

 

 

🥲 회고(?)

BufferedReader 을 사용해서 데이터를 입력 받고

데이터를 입력 받자마자 바로 구간 합 배열에 정보를 저장,

StringBuilder를 사용해 결과 값을 저장하는 지금의 코드와 달리,

 

코테 공부를 본격적으로 하기 전인 6달전에는

Scanner 로 데이터를 입력 받고 배열 arr에 전체 숫자를 입력 받은 뒤

arr을 끝까지 순회하며 max값을 찾으려고 했다. 

그 뒤, 구간 합 배열인 sum에 구간 합 정보를 저장하고 i와 j 범위의 합을

찾아 매 횟수마다 println으로 출력했다.

 

물론 지금 코드가 최고는 아니겠지만

BufferedReader를 이용해 데이터를 입력 받고

데이터를 입력 받자마자 바로바로 처리,

그리고 출력 정보는 StringBuilder 나 BufferedWriter 등을 이용해 저장하고

이후 한번에 출력해 메모리와 런타임을 줄이도록 하자