[자바] 백준 30646 -최대 합 순서쌍의 개수(java)

목차

문제 : boj30646

 

 

필요 알고리즘

• 누적 합(prefix sum), 해시를 사용한 집합과 맵
  
  • 누적합과 해시맵을 사용해 풀 수 있다. 물론 언제나 다른 방법들도 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  우선 누적합을 모른다면 '누적 합(prefix sum), 2차원 누적합(prefix sum of matrix) with java' 글을 보자.

이 문제를 풀기위한 로직을 생각해보면 다음을 알 수 있어야 한다.

 

  a값에 대해 의미있는건 각 a값이 최초로 나왔던 인덱스와 마지막에 나왔던 인덱스값이다. 예를들어 입력이 다음과 같다고 해보자.

5
1 1 1 1 1

 

  위의 입력에서 중요한건 a값이 '1'인 경우에 대해 최초로 나왔던건 첫번째이고, 마지막에 나왔던건 5번째라는 점이다. 왜냐하면 이 문제에서 a값은 항상 양의 정수이므로, 최대한 넓은 범위를 합치는게 언제나 이득이다. 즉 i=1, j=5 이외에 i=1, j=3인 경우 등은 아예 생각할 이유가 없다.

 

  그럼 위의 정보를 어떻게든 모두 알고 있다고 하자. 그럼 이제 효율적으로 특정 인덱스 사이에 존재하는 값들의 합을 알 수 있어야 한다. 이 때 가장 효율적인게 누적합 알고리즘이다.

 

 

정리하자면

1. N개의 a값에 대해, 서로 다른 a값들의 최초 인덱스와 마지막 인덱스를 기록한다. 이 때 a의 범위는 10^9개 이므로 배열로 하게되면 메모리 초과가 날꺼다. 그래서 HashMap을 사용해줬다. 그리고 입력값들은 미리 누적합 배열로 전처리해둔다. (arr[i] = arr[i-1]+cur;)

Map<Integer, Idx> idxes = new HashMap<>();
List<Integer> candidates = new ArrayList<>();

for (int i = 1; i <= n; i++) {
    int cur = Integer.parseInt(st.nextToken());
    if (!idxes.containsKey(cur)) {
        candidates.add(cur);
        Idx tmp = new Idx();
        idxes.put(cur, tmp);
    }
    idxes.get(cur).setValue(i);
    arr[i] = arr[i - 1] + cur;
}

  

2. 이제 서로다른 a값들에 대해 최초 인덱스와 마지막 인덱스 사이의 합을 구해서, 그 중 최대치와 최대치의 갯수를 찾아주기만 하면 된다.

long max = 0;
int cnt = 0;
for (int cur : candidates) {
    long sum = arr[idxes.get(cur).max] - arr[idxes.get(cur).min-1];
    if (sum < max) continue;
    if (sum == max) {
        cnt++;
        continue;
    }

    max = sum;
    cnt = 1;
}

System.out.println(max + " " + cnt);

 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        long[] arr = new long[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        Map<Integer, Idx> idxes = new HashMap<>();
        List<Integer> candidates = new ArrayList<>();

        for (int i = 1; i <= n; i++) {
            int cur = Integer.parseInt(st.nextToken());
            if (!idxes.containsKey(cur)) {
                candidates.add(cur);
                Idx tmp = new Idx();
                idxes.put(cur, tmp);
            }
            idxes.get(cur).setValue(i);
            arr[i] = arr[i - 1] + cur;
        }

        long max = 0;
        int cnt = 0;
        for (int cur : candidates) {
            long sum = arr[idxes.get(cur).max] - arr[idxes.get(cur).min-1];
            if (sum < max) continue;
            if (sum == max) {
                cnt++;
                continue;
            }

            max = sum;
            cnt = 1;
        }

        System.out.println(max + " " + cnt);
    }
}

class Idx {
    int min, max;

    public Idx() {
        this.min = Integer.MAX_VALUE;
        this.max = Integer.MIN_VALUE;
    }

    public void setValue(int num) {
        min = Math.min(min, num);
        max = Math.max(max, num);
    }
}