[BaekJoon] 19590 비드맨 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/19590

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int marbleTypeNum;
    static int[] marbles; // (index + 1)번 종류 구슬의 개수
    static PriorityQueue<Integer> maxHeap; // 구슬의 개수를 내림차순으로 정렬

    static void input() {
        Reader scanner = new Reader();

        marbleTypeNum = scanner.nextInt();
        marbles = new int[marbleTypeNum];
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        for(int idx = 0; idx < marbleTypeNum; idx++) {
            marbles[idx] = scanner.nextInt();
            maxHeap.offer(marbles[idx]);
        }
    }

    /*
        가장 큰 수를 기준으로 두 가지로 나눠볼 수 있다
            1. 가장 큰 수를 제외한 나머지 수의 합보다 가장 큰 수가 크거나 같은 경우
                - 가장 큰 수를 이용하여 다른 모든 구슬들과 부딪혀서 구슬을 없앤다
            2. 가장 큰 수를 제외한 나머지 수의 합보다 가장 큰 수가 작은 경우
                - 구슬 종류에서 구슬을 한 개씩, 총 두 개를 뽑아서 부딪혀서 구슬을 없앤다
                - 즉, 한 번 부딪힐 때 소모되는 구슬을 2개라는 뜻이다!
                - 그러므로 구슬의 전체 개수가 짝수라면 0개가 남을 것이고, 홀수라면 1개가 남을 것이다
                    - 최댓값이 나머지 구슬 수의 합보다 작은 경우이므로 짝수일 때 구슬이 남는 경우는 나타나지 않는다
     */
    static void solution() {
        long max = maxHeap.poll();
        long remainedSum = maxHeap.stream().mapToLong(Long :: valueOf).sum();

        if(max >= remainedSum) {
            System.out.println(max - remainedSum);
        } else {
            long totalNum = Arrays.stream(marbles).mapToLong(Long :: valueOf).sum();
            if(totalNum % 2 == 0) {
                System.out.println(0);
            } else {
                System.out.println(1);
            }
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}