[ BOJ ][JAVA][1933] 스카이라인

www.acmicpc.net/problem/1933

1933번: 스카이라인

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	1739	484	298	31.335%

문제

N개의 직사각형 모양의 건물들이 주어졌을 때, 스카이라인을 구해내는 프로그램을 작성하시오. 스카이라인은 건물 전체의 윤곽을 의미한다. 즉, 각각의 건물을 직사각형으로 표현했을 때, 그러한 직사각형들의 합집합을 구하는 문제이다.

예를 들어 직사각형 모양의 건물들이 위와 같이 주어졌다고 하자. 각각의 건물은 왼쪽 x좌표와 오른쪽 x좌표, 그리고 높이로 나타난다. 모든 건물들은 편의상 같은 높이의 지면(땅) 위에 있다고 가정하자. 위의 예에서 스카이라인을 구하면 아래와 같다.

입력

첫째 줄에 건물의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 N개의 건물에 대한 정보가 주어진다. 건물에 대한 정보는 세 정수 L, H, R로 나타나는데, 각각 건물의 왼쪽 x좌표, 높이, 오른쪽 x좌표를 의미한다. (1 ≤ L < R ≤ 1,000,000,000, 1 ≤ H ≤ 1,000,000,000)

출력

첫째 줄에 스카이라인을 출력한다. 출력을 할 때에는 높이가 변하는 지점에 대해서, 그 지점의 x좌표와 그 지점에서의 높이를 출력한다.

예제 입력 1

8
1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28

예제 출력 1

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0

코드

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

public class p1933 {
    static int n;
    static List<Building> list = new ArrayList<>();
    static class Building {
        int x, h;
        public Building (int x, int h) {
            this.x = x;
            this.h = h;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int lx = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            int rx = Integer.parseInt(st.nextToken());
            list.add(new Building(lx, h));
            list.add(new Building(rx, -h));
        }

        Collections.sort(list, new Comparator<Building>(){
            @Override
            public int compare(Building o1, Building o2) {
                // x높이가 다르다면 x 오름차순, x높이가 같다면 높이 내림차순
                if (o1.x == o2.x) {
                    return o2.h - o1.h;
                }
                return o1.x - o2.x;
            }
        });

        TreeMap<Integer, Integer> tm = new TreeMap<>(new Comparator<Integer>(){
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

        List<Building> ansList = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            Building cur = list.get(i);

            if (cur.h > 0) {
                tm.put(cur.h, tm.getOrDefault(cur.h, 0) + 1);
            } else {
                int key = -cur.h;
                int val = tm.get(key);
                if (val == 1) {
                    tm.remove(-cur.h);
                } else {
                    tm.put(key, val - 1);
                }
            }

            if (tm.size() == 0) {
                ansList.add(new Building(cur.x, 0));
                continue;
            }

            ansList.add(new Building(cur.x, tm.firstKey()));
        }

        bw.write(ansList.get(0).x + " " + ansList.get(0).h + " ");
        int prev = ansList.get(0).h;
        for (int i = 1; i < ansList.size(); i++) {
            if (prev != ansList.get(i).h) {
                bw.write(ansList.get(i).x + " " + ansList.get(i).h + " ");
                prev  = ansList.get(i).h;
            }
        }

        bw.write("\n");
        bw.flush();
        bw.close();
    }
}