BOJ 15970 - 화살표 그리기

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

15970번: 화살표 그리기

 

 

아이디어

색깔이 같은 점들 중 가장 가까운 점끼리의 거리를 구해야 하니까 일단 색깔별로 ArrayList에 분류한 후 정렬해준다.

 

정렬의 특성을 생각해보면 정렬 후 각 원소마다 가장 가까운 원소는 자신의 양 옆 중에 있다는 것을 알 수 있다. 가장 가까운 원소를 찾는다는 문구를 보고 정렬의 특성을 떠올려 정렬로 접근할 수 있어야 한다.

 

가장 가까운 점끼리의 거리를 구해야 하므로 기준 점의 왼쪽, 오른쪽 점까지의 거리를 비교해서 가장 가까운 점을 찾아낼 수 있다.

 

 

시간복잡도

색깔별로 정렬할 때 시간 복잡도가 O(N log N)이고, 가까운 점을 찾을 때 시간 복잡도가 O(N)이다.

N의 최댓값은 5000이므로 1초안에 가능한 풀이이다.

 

구현

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static ArrayList<Integer>[] dots;
    

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        dots = new ArrayList[N + 1];

        // 색깔별 리스트 생성
        for (int i = 1; i <= N; i++) {
            dots[i] = new ArrayList<Integer>();
        }

        // 색깔별로 분류해서 리스트에 add
        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            int point, color;
            point = Integer.parseInt(st.nextToken());
            color = Integer.parseInt(st.nextToken());

            dots[color].add(point);
        }

    }

    public static void pro() throws IOException {
        // 같은 색깔별로 정렬!
        for (int i = 1; i <= N; i++) {
            Collections.sort(dots[i]);
        }

        int ans = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < dots[i].size(); j++) {
                int left = toLeft(i, j);
                int right = toRight(i, j);

                // 양쪽 점 중 가장 가까운 점 찾기
                ans += Math.min(left, right);
            }
        }

        bw.write(ans+" ");
    }

    // 왼쪽 점과의 거리 구하기
    static int toLeft(int color, int idx) {
        if (idx == 0) {
            return Integer.MAX_VALUE;
        } else {
            return dots[color].get(idx) - dots[color].get(idx - 1);
        }
    }

    // 오른쪽 점과의 거리 구하기 
    static int toRight(int color, int idx) {
        if (idx == dots[color].size() - 1) {
            return Integer.MAX_VALUE;
        } else {
            return dots[color].get(idx + 1) - dots[color].get(idx);
        }
    }

    public static void main(String[] args) throws IOException {
        input();

        pro();

        bw.close();
    }
}