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

 

 

1학기 마지막 프로젝트도 끝내고...

하나금융티아이 1차 면접도 끝내고...

넘 오랜만에 알고리즘으로 돌아왔다 ㅠ

 

뭔가 그리웠음...

한 번 코테를 쳐봐서 그런지 제대로 코딩테스트를 준비하고 싶어져서

[무료] Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의

이 강의를 보며 100제 풀어보려고 한다!

 

내가 풀다가 처음보다시피 한 문제 풀이 방법이 있어 가져왔다.

바로 누적합 문제이다.

 

 

 

---

1. 출처

---

 

 

 

 

 

11659번: 구간 합 구하기 4

 

 

 

---

2. 설계

---

여기서 중요한 것은 1초 안에 최대 10만 번의 연산을 어떻게 해결할 것인가 이다.

단순히 for문으로 부분 합을 구하려고 했다면 시간 초과가 날 것이다.

바로 나처럼...

 

 

[시간 초과]

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();//수의 개수
		int M = sc.nextInt();//합을 구해야하는 개수
		
		int[] nums = new int[N];
		for(int i=0;i<N;i++) {
			nums[i] = sc.nextInt();
		}
		
		for(int i=0;i<M;i++) {
			int start = sc.nextInt();
			int end = sc.nextInt();
			long total = 0; //10만 수 10만개가 동시에 더해질 수 있음 
			for(int k=start-1;k<end;k++){
				total+=nums[k];
			}
			
			System.out.println(total);
		}

	}

}

 

그래서 누적합을 활용해줘야한다.

미리 0~1, 0~3 등 더했을 때의 결과를 저장해 두는 것이다.

예를들어  5 4 3 2 1 의 5개 숫자를 입력받았다고 가정하자. 그럼 누적합 배열에는

누적합[0] = 5

누적합[1] = 9

누적합[2] = 12

누적합[3] = 14

누적합[4] = 15

 

가 저장되는 것이다.

 

그렇다면 사용자가 1~2 부분의 합만 보고 싶다고 한다면, 0~1까지의 합을 보고 싶다고 한 것이다. 즉, 누적합[1] = 9를 출력해주면 된다.

또 다른 예시로 사용자가 2~4 부분의 합만 보고 싶다고 한다면, 1~3까지의 합을 보고 싶다고 한 것이다.

즉, 누적합[3]=14에서 시작 지점의 바로 앞 누적합[0]을 빼주면 14-5 = 9가 되는 것이다.

 

 

또 한 번 해보자! 만약 4~5 부분의 합을 보고 싶다고 한다면? (=3~4 범위)

누적합[4] - 누적합[2] = 15 - 12 = 3 이 정답이다.

 

즉 결론은!

start , end 지점을 입력 받아 누적합 배열의 end-1 지점에서 start-2 지점을 빼주면 된다.

누적합[end-1] - 누적합[start-2]

 

단, 시작지점이 1 즉, 0일 때, 가장 첫 부분부터 시작할 때는 누적합[end-1]만 출력해주면 정답이다.

 

 

 

---

3. 전체코드

---

import java.util.Scanner;

public class Main {
	//합배열을 이용하자!

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();//수의 개수
		int M = sc.nextInt();//합을 구해야하는 개수
		
		int[] nums = new int[N];
		long[] sumNums = new long[N];
		int sum=0;
		for(int i=0;i<N;i++) {
			nums[i] = sc.nextInt();//1 -> 2
			sum+=nums[i];//1 -> 3
			sumNums[i]=sum;//1 -> 3 -> 누적합 
		}
		
		StringBuilder sb = new StringBuilder();//결과 저장소 
		for(int i=0;i<M;i++) {
			int start = sc.nextInt();//1~
			int end = sc.nextInt();//3
			long result=0;
			
			//첫번째 인덱스부터 시작하지 않을때와 시작할 때 구분 
			if(start-1>0) {
				result = sumNums[end-1]-sumNums[start-2];
				sb.append(result).append("\n");
			}
			else {
				result = sumNums[end-1];
				sb.append(result).append("\n");
			}
			
		}
		
		System.out.println(sb);

	}

}

시간 더 아껴주려고 StringBuilder도 사용해보았다.