자바(백준) 15970 화살표 그리기

오답 노트 & 새로 아게 된 점

이 문제는 완탐으로 풀어도 아마 풀릴 것 같다.

그러나 정렬을 사용한다면 시간복잡도를 많이 줄일 수 있다.

 

여기서 색깔이 같은 점 중에 거리가 가장 가까운 점과 연결한다.

 

그래서 color가 같은 점들을 한 곳에 모아두고, 정렬을 시킨 뒤,

왼쪽 점과의 거리와 오른쪽 점과의 거리 중 최소를 구해 더하면 된다.

 

---

코드

 

import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N;
    static ArrayList<Integer> al[];
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        for (int i = 1; i <= N; i++) {
            Collections.sort(al[i]);
        }
 
        int sum = 0;
 
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < al[i].size(); j++) {
                sum += Math.min(goLeft(j, i), goRight(j, i));
            }
        }
 
        System.out.println(sum);
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = atoi(br.readLine());
 
        al = new ArrayList[N + 1];
 
        for (int i = 0; i <= N; i++) {
            al[i] = new ArrayList<>();
        }
 
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int position = atoi(st.nextToken());
            int color = atoi(st.nextToken());
 
            al[color].add(position);
        }
    }
 
    static int goLeft(int idx, int color) {
        if(idx == 0) return 1000000;
 
        return al[color].get(idx) - al[color].get(idx - 1);
    }
 
    static int goRight(int idx, int color) {
        if(idx == al[color].size() - 1) return 1000000;
 
        return al[color].get(idx + 1) - al[color].get(idx);
    }
}