[백준/Java] 15970 화살표 그리기

_

조건

1. 점들은 각각 색을 가지는데 그 색의 수는 N개이다.

2. 같은 색깔을 가진 점이 반드시 존재한다.

3. 같은 색의 점들 중 가장 가까운 점과 점끼리 화살표를 그린다.

4. 모든 점에서 시작하는 화살표의 수를 출력하라

코드

import java.io.*;
import java.util.*;

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int N;
    static ArrayList<Integer>[] a; 
//여기서 전체 배열을 탐색하며 각 색과 색을 비교하기에는 N * 2500 * 10의 5제곱이 걸린다.
//그렇기에 가장 먼저 할 것은 N개의 ArrayList를 생성하고 Color에 따라 그 배열로 각각 보낼 //것이다. 즉 N =4 라면 4개의 ArrayList가 생성되고 색에 따라 ArrayList에 Insert된다

    static void input() {
        N = scan.nextInt();
        a = new ArrayList[N + 1];
        for (int color = 1; color <= N; color++) { // N개의 수 만큼 배열 생성
            a[color] = new ArrayList<Integer>();
        }
        for (int i = 1; i <= N; i++) {
            int coord, color;
            coord = scan.nextInt();
            color = scan.nextInt();
            a[color].add(coord); // 정수 값을(점의 좌표) color에 맞게 넣어준다. 
        }
    }

    static int toLeft(int color, int idx) {
        if (idx == 0)  // 배열 index의 맨 앞의 경우 왼쪽에는 값이 없기에 정수 최소값을 return한다.
            return Integer.MAX_VALUE;
            
        return a[color].get(idx) - a[color].get(idx - 1); // 만약 앞에 값이 있다면 값을 빼 그 값을 return한다.
    }

    static int toRight(int color, int idx) {
        if (idx + 1 == a[color].size())  // 배열의 맨 마지막의 경우 더 이상 뒤가 없기 때문에 배열의 size + 1 에 도달하면 최대값을 return한다.
            return Integer.MAX_VALUE;
        return a[color].get(idx + 1) - a[color].get(idx); 
        //오른쪽이 있다면 idx + 1이 빼기의 앞으로 오게해 음수가 나오는 것을 막아준다.
    }

    static void pro() {
        for (int color = 1; color <= N; color++)
            Collections.sort(a[color]); //각각의 배열을 정렬한다.

        int ans = 0;
        for (int color = 1; color <= N; color++) {
            for (int i = 0; i < a[color].size(); i++) {
                int left_distance = toLeft(color, i);
                int right_distance = toRight(color, i);
                ans += Math.min(left_distance, right_distance); // 점과 점 사이의 거리를 비교하여 더 짧은 것을 ans에 더해준다.
            }
        }
        System.out.println(ans);
    }

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


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

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

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        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());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}