[백준] 2170번 - 선 긋기 [Java]

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

 

[백준] 2170번 - 선 긋기 [Java]

---

1.  아이디어

 

그리디 알고리즘과 스위핑 알고리즘으로 해결할 수 있었다.

---

2. 문제풀이

 

일반적인 그리디 알고리즘이랑 스위핑 두 가지 방식으로 접근했다.

그리디 알고리즘은 선의 x 좌표를 기준으로 오름차순 정렬한 우선순위 큐(items)와 y 좌표를 기준으로 내림차순 정렬한 우선순위 큐(pq) 두 개를 사용했다. items에서 원소(item)를 하나씩 꺼내서 pq의 원소(cur)와 비교하며 item과 cur이 겹치는 부분이 있으면 두 선을 합친 선을 pq에 다시 삽입하고 겹치는 부분이 없으면 각각 삽입하는 방식으로 구현했다. 이후 pq의 모든 선을 꺼내서 길이를 합하면 된다.

스위핑은 x 좌표를 기준으로 오름차순, x 좌표가 같으면 y 좌표를 기준으로 오름차순 정렬한 우선순위 큐 하나만 사용했고, 시작점과 끝점을 저장하는 변수 s, e를 사용했다. 우선순위 큐에서 원소를 하나씩 꺼내며 s, e로 이루어진 선과 겹치면 e의 위치만 갱신해주면 되고 겹치지 않으면 s, e의 위치를 갱신하고 선의 길이를 구하면 된다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {

    private static class Item {
        int s;
        int e;

        public Item(int s, int e) {
            this.s = s;
            this.e = e;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        PriorityQueue<Item> items = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.s, o2.s));
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            items.add(new Item(s, e));
        }

        PriorityQueue<Item> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o2.e, o1.e));
        pq.add(items.remove());

        while (!items.isEmpty()) {
            Item item = items.remove();
            Item cur = pq.remove();

            if (item.s > cur.e || item.e < cur.s) {
                pq.add(cur);
                pq.add(item);
            } else {
                pq.add(new Item(Math.min(cur.s, item.s), Math.max(cur.e, item.e)));
            }
        }

        int sum = 0;
        while (!pq.isEmpty()) {
            Item item = pq.remove();
            sum += item.e - item.s;
        }

        System.out.println(sum);
    }
}

import java.io.*;
import java.util.*;

public class Main {

    private static class Item implements Comparable<Item> {
        int s;
        int e;

        public Item(int s, int e) {
            this.s = s;
            this.e = e;
        }

        @Override
        public int compareTo(Item o) {
            if (this.s != o.s) return Integer.compare(this.s, o.s);
            return Integer.compare(this.e, o.e);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        PriorityQueue<Item> items = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            items.add(new Item(s, e));
        }

        int s = items.peek().s;
        int e = items.peek().e;
        items.remove();
        int sum = 0;

        while (!items.isEmpty()) {
            Item item = items.remove();

            if (item.s > e) {
                sum += e - s;
                s = item.s;
                e = item.e;
            } else {
                e = Math.max(e, item.e);
            }
        }
        sum += e - s;

        System.out.println(sum);
    }
}

---

4. 후기

 

- 그리디 알고리즘

- 스위핑