[15970] 화살표 그리기

🔗 문제 링크

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

🔍 문제 설명

직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(<그림 1>). 주어진 점들의 위치는 모두 다르다. 두 점 사이의 거리는 두 점의 위치를 나타내는 수들의 차이이다. <그림 1>에서는 4개의 점이 주어지고 점 a와 b의 거리는 3이다.

각 점은 N개의 색깔 중 하나를 가진다. 편의상, 색깔은 1부터 N까지의 수로 표시한다.

각 점 p에 대해서, p에서 시작하는 직선 화살표를 이용해서 다른 점 q에 연결하려고 한다. 여기서, 점 q는 p와 같은 색깔의 점들 중 p와 거리가 가장 가까운 점이어야 한다. 만약 가장 가까운 점이 두 개 이상이면 아무거나 하나를 선택한다.

모든 점에 대해서 같은 색깔을 가진 다른 점이 항상 존재한다. 따라서 각 점 p에서 시작하여 위 조건을 만족하는 q로 가는 하나의 화살표를 항상 그릴 수 있다.

예를 들어, 점들을 순서쌍 (위치, 색깔) 로 표시할 때, a = (0,1), b = (1, 2), c = (3, 1), d = (4, 2), e = (5, 1)라고 하자.

아래 <그림 2>에서 이 점들을 표시한다. 여기서 흰색은 1, 검은색은 2에 해당된다.

위의 조건으로 화살표를 그리면, 아래 <그림 3>과 같이 점 a의 화살표는 c로 연결된다. 점 b와 d의 화살표는 각각 d와 b로 연결된다. 또한 점 c와 e의 화살표는 각각 e와 c로 연결된다. 따라서 모든 화살표들의 길이 합은 3 + 3 + 2 + 3 + 2 = 13이다.

점들의 위치와 색깔이 주어질 때, 모든 점에서 시작하는 화살표들의 길이 합을 출력하는 프로그램을 작성하시오.

⚠️ 제한사항

• 모든 서브태스크에서 점들의 위치 x와 색깔 y는 각각 0 ≤ x ≤ 105, 1 ≤ y ≤ N를 만족한다.

🗝 풀이 (언어 : Java)

좌표와 색깔을 가지는 이차원 배열을 만들고, 1순위로 색깔기준, 2순위로 좌표 오름차순 기준으로 정렬한다. 반복문을 한번 돌면서 양끝 좌표인 케이스는 인접한 좌표와의 거리만 계산하고 중간의 좌표는 왼쪽과 오른쪽 좌표의 색깔을 비교해서 양쪽 다 같으면 좌표 거리 차이가 최소인 좌표, 한쪽만 같으면 해당 좌표 거리만 더해서 정답을 구한다. 시간복잡도는 Arrays.sort()를 사용해서 $O(NlogN)$일 것이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {
    private int drawArrow(int n, int[][] arr) {
        int answer = 0;
        // 색깔 기준으로 정렬하되, 같으면 좌표 오름차순으로 정렬
        Arrays.sort(arr, (o1, o2) -> {
            if (o1[1] == o2[1])
                return o1[0] - o2[0];
            else
                return o1[1] - o2[1];
        });
        // 반복문 돌면서 체크
        for (int i = 0; i < n; i++) {
            // 시작 좌표는 오른쪽 옆 점과의 거리
            if (i == 0) {
                answer += (arr[1][0] - arr[0][0]);
            // 마지막 좌표는 왼쪽 옆 점과의 거리
            } else if (i == n - 1) {
                answer += (arr[n-1][0] - arr[n-2][0]);
            } else {
                // 왼쪽 오른쪽 같은 색이면 좌표 거리차이 최소값
                if (arr[i][1] == arr[i-1][1] && arr[i][1] == arr[i+1][1])
                    answer += Math.min(arr[i][0] - arr[i-1][0], arr[i+1][0] - arr[i][0]);
                // 왼쪽만 같은 색
                else if (arr[i][1] == arr[i-1][1])
                    answer += (arr[i][0] - arr[i-1][0]);
                // 오른쪽만 같은 색
                else
                    answer += (arr[i+1][0] - arr[i][0]);
            }
        }
        return answer;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i] = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
        }
        br.close();
        Main main = new Main();
        System.out.print(main.drawArrow(n, arr));
    }
}