[백준 15975] - 화살표 그리기 Java

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

15975번: 화살표 그리기

 

문제를 정말정말 간단하게 요약하면

직선 위에는 서로 다른 위치의 N개의 점을 가지고 있는데,

각 점 p와 거리가 가장 가까우면서 색깔이 같은 다른 점 q를 연결한 거리를 구하는데, 색깔이 하나 뿐이라 연결 못 한 점은 0의 거리를 갖는다.

모든 거리의 합을 더하면 답이다.

풀이

위치와 색깔 정보가 무작위로 주어지는데, 같은 색깔의 점과 가장 가까이 있는 다른 점과의 거리를 계속 구해야한다.

N은 최대 100,000인데, 같은 색깔의 점들을 전부 $O(n^2)$로 탐색하면 시간 내에 탐색할 수 없다.

이 문제를 해결하기 위해 같은 색깔들끼리 모아두고, 같은 색깔들은 위치에 따라 정렬하면 정말 효율적으로 구할 수 있다.

예시

10 2
11 3
20 2
22 1
25 1
0 1
4 2
5 2
7 2

테스트 데이터를 같은 색깔끼리 정렬, 위치 순으로 나열한 결과는 다음과 같다.

0 1
22 1
25 1
4 2
5 2 
7 2
10 2
20 2
11 3

이제 문제 조건에 따라 확인해보면

 

색깔 1인 0번 위치의 구슬과 가장 가까이에 있는 구슬은 22번 위치가 된다.

22번 구슬은 0번과 25번을 확인해본 결과 25번과 더 가까이에 있는 것을 알 수 있다.

25번 구슬은 22번 구슬이 가장 가깝다.

색깔 2도 위와 마찬가지로 살펴본다.

 

위 내용을 구현하기 위해 위치정보, 색깔 정보를 가지는 클래스를 만들어줬다.

static class Point implements Comparable<Point> {
    int location, color;

    public Point(int location, int color) {
        this.location = location;
        this.color = color;
    }

    @Override
    public int compareTo(Point o) {
        if (this.color == o.color) {
            return Integer.compare(this.location, o.location);
        }
        return this.color - o.color;
    }
}

 

Comparable 인터페이스를 구현했고, 색깔별로 정렬, 색깔이 같은 경우에는 위치 순서대로 정렬하게 만들었다.

 

 

PriorityQueue<Point>에 모든 입력 데이터를 넣어주고, 하나씩 꺼내주면서 예시처럼 반복해 줬다.

int before = 0;
int beforeColor = -1;

while(!points.isEmpty()) {
    final Point poll = points.poll();
    if(poll.color != beforeColor) {
        before = poll.location;
        beforeColor = poll.color;
    }
    else {
        int diff = poll.location-before;
			//혹시 없으면 초기화 부분
        if(!map.containsKey(before)) {
            map.put(before, Integer.MAX_VALUE);
        }
        if(!map.containsKey(poll.location)) {
            map.put(poll.location, Integer.MAX_VALUE);

        }
			//초기화 상태거나, 더 짧은 거리가 존재하면 교체
        if(map.get(before)>diff)
            map.replace(before,diff);
        if(map.get(poll.location)>diff)
            map.replace(poll.location, diff);

        before = poll.location;

    }
}

map에 위치별로 최단 거리 값을 저장하면서 진행한다.

 

전체 코드

package 백준_2024년.스터디_5wnck;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class problem2 {
    static class Point implements Comparable<Point> {
        int location, color;

        public Point(int location, int color) {
            this.location = location;
            this.color = color;
        }

        @Override
        public int compareTo(Point o) {
            if (this.color == o.color) {
                return Integer.compare(this.location, o.location);
            }
            return this.color - o.color;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        HashMap<Integer, Integer> map = new HashMap<>();
        PriorityQueue<Point> points = new PriorityQueue<>();

        for(int i= 0;i<N;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int location = Integer.parseInt(st.nextToken());
            int color = Integer.parseInt(st.nextToken());
            points.add(new Point(location, color));
        }

        int before = 0;
        int beforeColor = -1;

        while(!points.isEmpty()) {
            final Point poll = points.poll();
            if(poll.color!=beforeColor) {
                before = poll.location;
                beforeColor = poll.color;
            }
            else {
                int diff = poll.location-before;
                if(!map.containsKey(before)) {
                    map.put(before, Integer.MAX_VALUE);
                }
                if(!map.containsKey(poll.location)) {
                    map.put(poll.location, Integer.MAX_VALUE);

                }
                if(map.get(before)>diff)
                    map.replace(before,diff);
                if(map.get(poll.location)>diff)
                    map.replace(poll.location, diff);

                before = poll.location;

            }
        }

        long sum = 0;

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            sum+=entry.getValue();
        }
        System.out.println(sum);

    }
}