[Java] 백준 15975. 화살표 그리기

문제 

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

15975번: 화살표 그리기

풀이

우선 색깔 별로 정렬을 한다. 같은 색깔이면, 좌표순 오름차순 정렬. 

그 다음 O(N)으로 탐색 하면서, 현재 위치 i 에서 left = i-1 , right = i+1 을 꺼내서 비교를 해준다.

ArrayList<int[]> Info = new ArrayList<>(); // 이런식으로 2차원 리스트를 받는다. 

Collections.sort(Info, (a,b)->a[1] == b[1] ? a[0]-b[0] : a[1]-b[1]);//색깔별, x좌표순 별 정렬

 

현재 정점 포인트 i 에서 left 와 i , right 와 i 각각 색깔이 같아야 하고, 인덱스 범위를 지켜야 한다.

이때 누적합 ans 는 long형임에 주의하자.

 

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        FastReader fr = new FastReader();
        //입력받기
        int N= fr.nextInt(); //점의 개수

        ArrayList<int[]> Info = new ArrayList<>();
        int colorSize[] = new int[N+1];
        for(int i =0 ;i < N ;i++){
            int x = fr.nextInt();
            int color = fr.nextInt();
            Info.add(new int[]{x,color});
            colorSize[color]++;
        }
        Collections.sort(Info, (a,b)->a[1] == b[1] ? a[0]-b[0] : a[1]-b[1]);//색깔별, x좌표순 별 정렬
        long ans = 0;

        for(int i = 0 ;i < Info.size() ;i++){
            if (colorSize[Info.get(i)[1]] > 0) {
                int left = Integer.MAX_VALUE;
                int right = Integer.MAX_VALUE;
                int ldx = i-1;
                int rdx = i+1;
                if(ldx >= 0 && Info.get(ldx)[1] == Info.get(i)[1]){
                    left = Info.get(i)[0]-Info.get(ldx)[0];
                }
                if(rdx < Info.size() && Info.get(rdx)[1] == Info.get(i)[1]){
                    right = Info.get(rdx)[0] - Info.get(i)[0];
                }
                int v = Math.min(left,right);
                ans += v != Integer.MAX_VALUE ? v : 0;
            }
        }
        System.out.println(ans);

    }

    public 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;
        }
    }
}