백준 1933 자바 - 스카이라인

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

1933번: 스카이라인

문제

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

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

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedWriter bw  = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        List<Building> buildings = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            buildings.add(new Building(l, h));
            buildings.add(new Building(r, -h));
        }
        buildings.sort(new Comparator<Building>() {
            @Override
            public int compare(Building o1, Building o2) {
                if (o1.x == o2.x) {
                    return o2.h - o1.h;
                }
                return o1.x - o2.x;
            }
        });

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

        List<Building> answer = new ArrayList<>();
        for (int i = 0; i < buildings.size(); i++) {
            Building building = buildings.get(i);
            if(building.h > 0) {
                tree.put(building.h, tree.getOrDefault(building.h, 0) + 1);
            } else {
                int key = -building.h;
                int val = tree.get(key);
                if (val == 1) {
                    tree.remove(-building.h);
                } else {
                    tree.put(key, val - 1);
                }
            }
            if (tree.size() == 0) {
                answer.add(new Building(building.x, 0));
                continue;
            }
            answer.add(new Building(building.x, tree.firstKey()));
        }
        bw.write(answer.get(0).x + " " + answer.get(0).h + " ");
        int previous = answer.get(0).h;
        for (int i = 0; i < answer.size(); i++) {
            if (previous != answer.get(i).h) {
                bw.write(answer.get(i).x + " " + answer.get(i).h + " ");
                previous = answer.get(i).h;
            }
        }
        bw.flush();
    }

    private static class Building {
        int x;
        int h;

        public Building(int x, int h) {
            this.x = x;
            this.h = h;
        }
    }
}

풀이

겹쳐진 빌딩들에서 높이는 지금까지 나온 점들 중 가장 높은 빌딩의 높이를 따라간다. 높이로 정렬해주는 자료구조를 사용해야 한다. 겹쳐진 빌딩들 중 마지막 빌딩에 대해서는 연산을 하지 않기 위해 빌딩의 시작점과 끝점을 구분해 모두 저장한다. (+와-로 구분) 시작점의 경우 자료구조에 넣어 갱신한다. 끝점은 시작점의 높이를 제거해준다. 계속 탐색해 가장 높은 높이들은 정답을 저장하는 자료구조(answer)에 넣어주고 최종적으로 출력한다.