문제 이해

0 ~ $10^5$ 위치에 중복하지 않는 N개의 점이 존재한다
이 때, 모든 점에서 자신과 같은 색깔의 점 중 거리상으로 가장 가까운 점을 찾는다.
이후 모든 점에 대해 자신과 가장 가까운 점과의 거리를 구하고, 이렇게 구한 거리의 합을 출력한다.

무조건 같은 색깔의 점은 2개 이상 존재하기 때문에 자신과 동일한 색의 점이 없는 경우는 고려하지 않아도 된다.

문제 풀이

먼저 색깔이 흰색 점과 검은색 점만 있는 경우를 생각해보자. Array를 2개 생성하자.
arr[1]에는 흰색 점들만, arr[2]에는 검은색 점들만 저장하자.
이후 arr[1]과 arr[2]를 위치 값을 기준으로 Sort시킨다.

A번째 index에 위치한 값과 가장 가까운 점은 A-1번째 index 혹은 A+1번째 index에 존재할 것이다.
(A-2번째 이하에 존재하는 점보다는 A-1번째에 존재하는 점이 가깝고, A+2번째 이상에 존재하는 점보다는 A+1번째에 존재하는 점이 가깝기 때문 → Sorting의 특성)
따라서, arr[1]과 arr[2]의 모든 원소에 대해 A-1, A+1번째 index 값들과 비교하여 더욱 가까운 거리에 위치하는 점을 선택하고, 선택한 점과의 거리를 합쳐서 출력하면 된다.

마지막으로, 점의 색깔은 최대 N개가 존재할 수 있다.
따라서 Array는 총 N개 준비되어야 할 것이다.

코드

import java.util.*;

public class Main {
	
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		ArrayList<Integer>[] lists = new ArrayList[N+1];
		
		for(int i = 1;i<N+1;i++) {
			lists[i]= new ArrayList<Integer>();
		}
		
		int a,b;
		for(int i =0;i<N;i++) {
			a = sc.nextInt();
			b = sc.nextInt();
			
			lists[b].add(a); 
            // 같은 색깔을 가지고 있는 점들만 한 개의 ArrayList에 모음
		}

		int answer = 0;
		int tmp2;

		for(int i =1;i<N+1;i++) {
			if(lists[i].isEmpty()) {
            // 색깔은 N개 이하이지만, 꼭 N개는 아니기 때문에 
            // 빈 ArrayList가 존재할 수 있음
				continue;
			}

			int tmp = Integer.MAX_VALUE;
			Collections.sort(lists[i]); // Sorting하는 과정

			for(int j = 0;j<lists[i].size() - 1;j++) {
				tmp2 = lists[i].get(j+1)-lists[i].get(j);
				tmp = Math.min(tmp, tmp2);
				answer+=tmp;
				tmp = tmp2;
                /*
                tmp : j번째와 j-1번째 index 점과의 거리
                tmp2 : j번째와 j+1번째 index 점과의 거리
                
                tmp와 tmp2중 더 작은 값이 최소의 거리가 될 것이므로 
                answer에 더해준다.
              
                j번째와 j+1번째의 거리는 j+1을 K라고 보았을 때 
                K-1번째와 K번째의 거리이다.
                따라서, K-1과 K사이의 거리를 다시 계산하지 말고 
                이전에 계산했던 값을 활용하자.
                이를 위해 tmp에 tmp2 값을 저장하여 다음 for문에 활용한다.
                */
			}

			answer+=tmp;
            /*
            ArrayList의 마지막 index를 T라고 생각하자.
            이 때 T+1 index 위치에는 값이 존재하지 않기 때문에
            무조건 T번째 점과 가장 가까운 점은 T-1번째 점이 될 것이다.
            위에서 T-1번째와 T번째 거리는 tmp에 저장되어 있다고 했다. 
            따라서 이를 더해준다.
            */
		}

		System.out.println(answer);
	}
}

결과