[Java] 부분합 알고리즘

1. 문제 설명

N개의 숫자카드를 선정해 임의의 순서로 배치
숫자카드의 순서는 바뀌지 않으며 1, 2, ... N로 번호를 붙임(인덱스)
각 카드에는 32비트 정수형 범위에 해당하는 숫자가 적혀있다. 다만 공개 X
한사람당 한 번만 카드를 골라 1 ~ N 사이의 L, R을 고를수 있다

{1, -1, 5, 2, 3} -> L = 2, R = 4를 고른 사람은 -1 + 5 + 2

M명의 사람이 카드를 고를 때 가장 높은 점수를 차례로 선정해 초대장을 줄 때
가장 먼저 초대장을 받게될 사람 숫자카드를 몇번째로 뽑은 사람일까?

입력형식

첫 줄에 숫자카드 개수(N)와 선택할 사람(M)을 입력 (n,m 모두 1 ~10만)
두 번째 줄에는 N개의 32비트 정수 입력
그 후 M개의 L과 R을 입력

출력형식

한 줄에 가장 먼저 초대장을 받게 될 사람이 앨범을 구매한 순서와 얻은 점수를 출력한다. 같은 점수를 얻은 사람이 존재 할 경우 먼저 구매한 사람을 기준으로 출력한다.

2. 알고리즘 접근

M명의 사람이 L과 R을 선택하고 그 점수를 가지고 있어야한다 또한 답을 도출할 때 숫자카드를 뽑은 순서를 요구하기 때문에 클래스로 4개의 필드를 정의하고,
객체 배열을 이용해 M명의 사람의 데이터를 관리하자

숫자카드를 배열로 정의하고 이를 L ~ R까지 탐색하여 sum을 해준다
이 때 32비트 정수형의 합이므로 int를 초과할 수 있기에 64비트 정수형을 사용한다
그리고 이 때 L ~ R값을 반복문을 통해 탐색하여 도출한다면 시간에러(O(M x N))가 난다
이를 해결 하는 방법을 소개하겠다

누적합 배열 사용

cards[1, -1, 5, 2, 3] // 숫자카드 배열을 인덱스마다 더해준다
[1, 1 - 1, 1 - 1 + 5, 1-1+5+2, 1-1+5+2+3]
rangesum[1, 0, 5, 7, 10] // 숫자카드의 합을 배열에 넣어준다

위의 방식으로 한다면 반복을 처음부터 할 필요없이 앞의 반복한 값을 이용할 수 있다
rangesum[2] = rangesum[1] + cards[2]
rangesum[3] = rangesum[2] + cards[3]

그러면 의문이 들 수 있다 어? 저희는 1부터의 누적합이 아닌 left ~ right까지 누적합인데요
이는 응용하면 쉽게 풀리는 문제다

r.totalPoint = rangeSum[r.right] - rangeSum[r.left-1];
left ~ right의 범위  == rangeSum - (1 ~ left이전의 합)

위와 같이 해결 할 수 있다

Sum값을 도출한 후 각 값마다 비교하여 max값을 구해 답을 도출한다
(이 때 중복에 대한 예외로 인덱스가 빠른 값을 도출하자 (먼저 구매한사람))

3. 알고리즘 풀이

package algorithm.comon.chapter3;

import java.util.Scanner;

public class Q3F {
    public static final Scanner sc = new Scanner(System.in);
    private static Range getBestRange(int n, int m, int[] cards, Range[] range) {
        Range answer = range[0]; // 정답 초기화

        // 누적합 배열 생성
        long[] rangeSum = new long[n + 1]; // 인덱스 0은 제외한다
        rangeSum[0] = 0; // 자바는 생략해도 되지만 가독성을 위해
        // 누적합 배열을 활용한 구간합 순회
        for(int i = 1; i <= n; i++){
            // rangeSum을 채우자
            rangeSum[i] = rangeSum[i - 1] + cards[i];
        }


        for(Range r : range){ // 모든 객체에 대해서
            // r.totalpoint = cards[r.left] ~ card[r.right]의 구간합
            r.totalPoint = rangeSum[r.right] - rangeSum[r.left - 1]; //left 이전까지의 합을 뺀다
            if(answer.totalPoint < r.totalPoint){
                answer = r;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        int n = sc.nextInt(); // 숫자카드 개수 입력
        int m = sc.nextInt(); // 숫자카드를 선택한 사람 수

        Range[] range = new Range[m]; // 사람이 선택한 정보를 담을 객체배열

        int[] cards = new int[n+1];  // 인덱스값을 1로 맞추기 위해 공간을 하나 더 할당
        for(int i = 1; i <= n; i++){
            cards[i] = sc.nextInt(); // 32비트 정수값을 입력
        }

        for(int i = 0; i < m; i++){
            int left = sc.nextInt(); // 선택한 L값 입력
            int right = sc.nextInt(); // R값 입력
            range[i] = new Range(i + 1, left, right);
            // 결과를 도출하기 위해서 몇번째로 선택한지 알아야하기에 인덱스번호를 객체에 저장한다
        }

        // 범위의 합이 가장 큰 범위를 계산
        Range answer = getBestRange(n, m, cards, range);
        System.out.printf("%d %d\n", answer.index, answer.totalPoint);

    }
}
// 회원이 입력한 값을 가지고 있는 클래스
class Range{
    int index;
    int left;
    int right;
    long totalPoint; // 32비트 정수값이 오바될 수 있으니 Long

    Range(int index, int left, int right){
        this.index = index;
        this.left = left;
        this.right = right;
        this.totalPoint = 0;
    }

}

클래스를 이용한 문제 풀이에 익숙해질 수 있는 시간이었다
누적합은 항상 Left ~ right 반복을 통해 풀었는데
이번에는 아예 누적합한 배열을 정의해 이를 활용하여 시간복잡도를 O(N + M)으로
단축시킬 수 있다는 개념을 배웠다 (복습을 통해 익숙해지자)