[S4] 화살표 그리기

문제 풀이

직선 위에 점은  위치와 색깔을 나타낸다. (위치,색깔) 위치는 최대 10만까지 색깔은 300개까지  최대 가능하다. 점을 지나칠때 마다 모두 검사를 한다면 제한 시간 2초 (약 2억번)에는 불가능하다. 이유는 O(n) * n 이기 때문에 2억번을 넘는다. 그렇기 때문에 색상 별로 나누고 정렬한다.  가장 가까운 원소는 양 옆에 있기 때문에 하나를 고르면 된다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class 화살표그리기_15970 {
    static StringBuilder sb = new StringBuilder();
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static ArrayList[] lists;
    static StringTokenizer st;
    static int T, sum;

    public static void main(String[] args) throws IOException {
        init();
        calc();
        sb.append(sum);
        System.out.println(sb.toString());
    }

    private static void calc() {
        for (int j = 1; j <= T; j++) {
            for (int i = 0; i < lists[j].size(); i++) {
                if (i == 0) {
                    sum += lists[j].get(1) - lists[j].get(i);
                } else if (i == lists[j].size() - 1) {
                    sum += lists[j].get(i) - lists[j].get(i - 1);
                } else {
                    sum += Math.min(lists[j].get(i) - lists[j].get(i - 1), lists[j].get(i + 1) - lists[j].get(i));
                }
            }
        }

    }

    private static void init() throws IOException {
        T = Integer.parseInt(br.readLine());
        lists = new ArrayList[T + 1];
        for (int i = 1; i <= T; i++) {
            lists[i] = new ArrayList<>();
        }
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine());
            int point = Integer.parseInt(st.nextToken());
            int color = Integer.parseInt(st.nextToken());
            System.out.println("point : " + point + " , color : " + color);
            lists[color].add(point);
        }

        for (int i = 1; i <= T; i++) {
            Collections.sort(lists[i]);
        }
    }
}

 

www.acmicpc.net