[Java] BOJ/백준 2170번 선 긋기

[문제]

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

2170번: 선 긋기

 

[풀이]

이 문제의 핵심은 아래 두 가지로 요약할 수 있다.

1. 선을 좌표 기준으로 정렬해야된다. (우선순위 큐 혹은 배열 정렬)

2. 선이 포함되는 경우 조건문으로 처리

 

👎 배열에 선을 그은 곳은 1로 채워 총 1의 수를 구할 경우, 배열 크기를 2조로 지정해야되기 때문에 다른 방법을 생각해야한다.

 

문제에서 주어진 입력된 선을 형광펜으로 표시하면 이렇다.

 

1️⃣ 선 좌표 기준 정렬

문제에서는 연결되어있는 선이 있고 아닌 선이 있기 때문에 이를 구분해주기 위해 두 점의 위치를 기준으로 정렬해야한다.

Coordinate 클래스는 Comparable 인터페이스를 상속받아 compareTo 메서드를 오버라이드 해야하는데, x 좌표를 기준으로 오름차순 정렬을 하고, x 좌표가 같을 경우 y 좌표를 기준으로 오름차순 정렬을 하도록 오버라이드 해주었다.

static class Coordinate implements Comparable<Coordinate> {
        int x, y;

        public Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Coordinate o) {
            if (this.x == o.x) return this.y - o.y;
            else return this.x - o.x;
        }
}

문제의 각 x, y 좌표를 Coordinate 객체를 생성해 Priority Queue에 넣으면 좌표를 기준으로 정렬된 우선순위 큐가 생성된다.

---

2️⃣ 조건문 처리

분홍 선: 이전에 그어진 선,  보라 선: 지금 긋는 선

1. 지금 선이 이전 선에 완전히 포함되어 있을 때

지금 선인 (2, 4)는 이전 선 (1, 6)에 완전히 포함되기 때문에 무시한다.

 

2. 이전 선과 지금 선이 겹치지 않을 때

y 좌표에서 x 좌표를 뺀 값을 더한다.

answer += 6 - 5

 

3. 이전 선과 지금 선이 겹치고, 지금 선의 y 좌표가 더 길 때

현재 선의 y 좌표에서 이전 선의 y 좌표를 뺀 값을 더한다.

answer += 6 - 4

 

[코드]

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

public class Main {

    static class Coordinate implements Comparable<Coordinate> {
        int x, y;

        public Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Coordinate o) {
            if (this.x == o.x) return this.y - o.y;
            else return this.x - o.x;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        PriorityQueue<Coordinate> pq = new PriorityQueue<>();
        StringTokenizer st;
        while (N-- > 0) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            pq.offer(new Coordinate(x, y));
        }

        Coordinate first_line = pq.poll();
        int start = first_line.x;
        int end = first_line.y;
        int answer = end - start;
        while (!pq.isEmpty()) {
            Coordinate cur_line = pq.poll();
            if (end < cur_line.x) {	// 선이 인접하지 않을 때
                start = cur_line.x;
                end = cur_line.y;
                answer += end - start;
                continue;
            }
            if (cur_line.y > end) {	// 선이 인접하고 지금 y 좌표가 더 길 때
                answer += cur_line.y - end;
                end = cur_line.y;
            }
        }
        System.out.println(answer);
    }
}