[BOJ 15970] 화살표 그리기 (java)

 

 

 

---

문제 링크

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

15970번: 화살표 그리기

---

풀이

- 첫째줄에 점 N개가 주어지고, 다음 라인 부터 N개만큼 "위치 색깔" 형태로 입력이 주어짐 

- 같은 색깔에 p와 q점에 대해 직선 화살표로 연결하려 할 때, 가장 가까운 거리의 점이여야 함 (만약 가까운 점이 두 개 이상이면 둘중 아무거나 선택)

- 모든 점에 대해 같은 색깔을 가진 다른 점이 항상 존재 ( 2 <= N <= 5000)

 

기준점에서 왼쪽, 오른쪽에 같은 색상의 점이 있을 때 양쪽 거리 값 구한 후 최소값이 되는 방향으로 화살표 그림
이때 시작점과 끝점은 한쪽 방향만 구해짐

 

최대값 

- 점 (최대 10만, o <= x <= 10^5)

- 색깔(최대 5000, 1 <= y <= N)

- 5000 * 10만(=10만 - 0) = 5 * 10^8 = 5억이므로 integer로 충분

 

시간 복잡도 : O(NlogN), 정렬 후 원소 개수만큼 반복문 수행함

공간 복잡도 : O(N)

---

풀이 코드

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

class Main {
    static int N;
    
    static List<Integer>[] A;
    
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        A = new ArrayList[N + 1];
        for(int i = 1; i <= N; i++) {
            A[i] = new ArrayList<>();
        }

        for(int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int point = Integer.parseInt(st.nextToken());
            int color = Integer.parseInt(st.nextToken());

            A[color].add(point);
        }

        br.close();
    }

    static int calLeft(List<Integer> arr, int idx) {
        if(idx == 0) return Integer.MAX_VALUE;

        return arr.get(idx) - arr.get(idx - 1);
    }

    static int calRight(List<Integer> arr, int idx) {
        if(idx == arr.size() - 1) return Integer.MAX_VALUE;

        return arr.get(idx + 1) - arr.get(idx);
    }
    static void pro() {
        for(int i = 1; i <= N; i++) Collections.sort(A[i]);

        int ans = 0;
        for(int i = 1; i <= N; i++) {
            if(A[i].size() > 0) {
                for(int j = 0; j < A[i].size(); j++) {
                    int left = calLeft(A[i], j);
                    int right = calRight(A[i], j);

                    ans += Math.min(left, right);
                }
            }
        }

        System.out.println(ans);
    }

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