[백준]11659 구간 합 구하기 - Java/자바

11659번: 구간 합 구하기 4

풀이

• 메모리 252892KB, 시간 1272ms
• 어려운 문제는 아니었는데, 인덱스 관련 처리가 약간 헷갈렸다.그래서 if문 처리 했는데 이럴 필요 없이 애초에 인덱스를 조절하면 되는 문제였음
• a부터 b까지의 합을 구하라하면 sums[b] - sums[a-1]이 되어야 값이 나오는데, 이 때 a가 0이면 인덱스 범위 오류가 발생한다.
• 문제에서 주어진대로, 범위 i와 j가 1부터 시작하므로 구간합도 인덱스가 1일 때 최초의 값으로 설정하면 코드가 더 간단해진다. 아~주 약간의 메모리를 더 잡아먹지만 이건;; 쓰는게 정신건강에 나은 수준
• 물론 nums[0]와 sums[0]은 0으로 초기화해줘야한다.
• 그리고 System.out.println()으로 출력하면 깔끔하지가 않아서 StringBuilder가 생각 안나서 BufferedWriter쓰기도 하고 줄바꿈이 기억 안나서 \\br로 적기도 하고 참.. 쉽게 까먹는다.

import java.util.Scanner;

/*
 * TAG: 구간합, 기초
 */
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int N = sc.nextInt(); // 수의 개수
		int M = sc.nextInt(); // 합을 구해야 하는 횟수
		int[] nums = new int[N];
		long[] sums = new long[N];
		for(int i = 0; i<N; i++) {
			nums[i] = sc.nextInt();
			if(i == 0) sums[i] = nums[i];
			if(i>0) sums[i] = nums[i]+sums[i-1]; //구간합
		}
		
		for(int i = 0; i<M; i++) {
			int st = sc.nextInt()-1;
			int ed = sc.nextInt()-1;
			int leng = ed-st-1;
			if(st == 0) sb.append(sums[ed]+"\\n");
			else sb.append(sums[ed]-sums[st-1]+"\\n");
		}
		
		System.out.print(sb.toString());
		sc.close();
	}
}

---

 

코드 리뷰

• 로직 자체는 나보다 나은데 오히려 연산이 더 줄어야 하지 않나..? 싶은데 시간이 2배다.
• 아마 출력할 때 매 값마다 System.out.println()을 사용해서 그런 것 같다.엥간하면 StringBuilder를 사용해야겠다.
• StringBuilder를 사용하면 모아서 한번에 출력하니 시간이 많이 아껴지는 듯

💡 풀이자 : taky0315, 메모리 : 250200KB, 시간 2592ms

import java.util.*;

public class Main {
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();  //숫자의 개수
		int m = sc.nextInt();  //계산 몇번할지
		
		int[] arr = new int[n + 1];
		int[] sum = new int[n + 1];
		sum[0] = 0;
		arr[0] = 0;
		for(int i=1; i<n+1; i++)
		{
			arr[i] = sc.nextInt();
			if(i == 1)
			{
				sum[i] = arr[i];
			}
			else
			{
				sum[i] = sum[i - 1] + arr[i];
			}
		}
		
		//계산하기.
		for(int i=0; i<m; i++)
		{
			int n1, n2;
			n1 = sc.nextInt();
			n2 = sc.nextInt();
			System.out.println(sum[n2] - sum[n1 -1]);
		}
	}
}

 

 

• 메모리는 1/4수준이고 시간은 절반 단축됐다.
• BufferedReader와 StringBuilder를 사용해서 시간과 용량이 단축된 듯?
• 구간합 배열만 한 크기 더 늘려 선언해서 코드를 간소화 했다는 점이 주목할만하다.인덱스 기준 sum 배열은 1부터 유효한 값이 존재하고 nums 배열은 0부터 유효한 값이 존재한다.
• 즉 sum[1]이라고 하면 첫 번째 값 까지의 구간합, sum[3]은 세번째 값 까지의 구간합이다. 인덱스가 달라서 헷갈릴 수 있는데 말로 정리하면 외려 더 직관적인듯
• sum[i + 1] = sum[i] + nums[i] 에서 i가 0이면 sum[1] = sum[0] + nums[0] i가 1이면 sum[2] = sum[1] + nums[1] 이므로 구간합 배열이 발생한다.

💡 풀이자 : zkdlajt1 메모리 : 59716KB, 시간 656ms

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nm = br.readLine().split(" ");
        int n = Integer.parseInt(nm[0]);
        int m = Integer.parseInt(nm[1]);

        String[] numString = br.readLine().split(" ");
        int[] nums = new int[n];
        int[] sum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(numString[i]);
            sum[i + 1] = sum[i] + nums[i];
        }

        StringBuilder sb = new StringBuilder();
        for (int k = 0; k < m; k++) {
            String[] ij = br.readLine().split(" ");
            int i = Integer.parseInt(ij[0]);
            int j = Integer.parseInt(ij[1]);
            sb.append(sum[j] - sum[i - 1]).append("\\n");
        }
        System.out.print(sb);
    }
}

---

 

Conclusion

• 누적합, 구간합 배열은 주어지는 숫자 배열의 크기보다 +1해서 선언하는게 더 간편한다.
• Scanner 함수, System.out.println은 생각보다 시간, 메모리를 많이 잡아먹는다.
• StringBuilder, BufferedReader, BufferedWriter는 시간과 메모리를 많이 아껴준다.