[JAVA] 백준 15970번 : 화살표 그리기(한국정보올림피아드/KOI 2018/초등부)

www.acmicpc.net/problem/15970

15970번: 화살표 그리기

문제

각 점에서 색깔이 같은 가장 가까운 점과 연결한 화살표들의 길이 합을 구하는 문제이다.

 

해결 방안

색깔마다 점의 배열을 만들어서 정렬을 한 뒤 각 점에서 가장 가까운 선(왼쪽 혹은 오른쪽)을 구해서 더해주면 되겠다고 생각하였다.

HashMap을 사용하여 점들의 색깔마다 ArrayList(점의 위치 배열)를 만들어주었다.

그 후 색깔마다 점의 위치 배열을 정렬해주고 각 점에서 가장 가까운 점까지의 화살표 길이를 더해주었다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class Main {

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N; // 점들의 갯수
		int x; // 점의 좌표
		int y; // 점의 색깔
		String str = br.readLine();
		N = Integer.parseInt(str);
		
		Map<Integer, ArrayList<Integer>> map = new HashMap<>();
		for(int i=0; i<N; i++) {
			str = br.readLine();
			x = Integer.parseInt(str.split(" ")[0]);
			y = Integer.parseInt(str.split(" ")[1]);
			
			// 색깔별 점의 좌표
			if(map.containsKey(y)) {
				map.get(y).add(x);
			}
			else {
				map.put(y, new ArrayList<Integer>());
				map.get(y).add(x);
			}
		}
		
		int sum = 0;
		Set<Integer> keys = map.keySet();
		// 1~N
		for(int key: keys) {
			ArrayList<Integer> arr = map.get(key);
			Collections.sort(arr);
			
			int distance = 0;
			int l=0;
			int r=0;
			for(int i=0; i<arr.size(); i++) {
				if(i==0) {
					distance = arr.get(i+1)-arr.get(i);
				}
				else if(i==arr.size()-1) {
					distance = arr.get(i)-arr.get(i-1);
				}
				else {
					l = arr.get(i)-arr.get(i-1);
					r = arr.get(i+1)-arr.get(i);
					distance = Math.min(l, r);
				}
				sum += distance;
			}
		}
		System.out.println(sum);
	}

}