[BOJ 1933] 스카이라인(Java, Treemap, 설명, 간단한 코드)

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

1933번: 스카이라인

---

 

스카이라인을 형성할 때, 위의 건물들의 각 시작점과 끝점을 살펴보면 가장 높은 건물의 높이를 따라가게 되어있다.

 

 

 

즉. 빨간색으로 표시한 점들을 모두 조사해서 걸쳐진 빌딩 중 가장 높은 높이를 표기해주면 된다. 

 

 

 

걸쳐진 빌딩 중 가장 높은 높이를 찾는 방법은, 높이를 내림 차순으로 정렬하는 자료구조를 사용해야 한다.

 

 

 

또한 끝난 빌딩의 높이에 대해서는 연산하지 않기 위해서, 시작점과 끝점을 구분해서 모든 점들을 탐색해야 한다.

 

 

 

시작점인 경우, 자료구조에 넣어서 높이를 갱신하고, 끝점인 경우에는 해당 시작점 관련 높이를 제거해주면 된다.

 

 

 

모든 점들을 탐색하면서, 가장 높은 높이들은 정답을 만드는 자료구조에 넣어준다.

 

 

 

정답을 출력할 때는, 고도가 변하는 경우에만 출력해주면 된다.

---

해설코드(Java).

import java.io.*;
import java.util.*;
 
class Building{
    int x;
    int h;
    
    public Building(int x, int h) {
        this.x = x;
        this.h = h;
    }
}
 
public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);
    public static StringTokenizer st;
    public static List<Building> buildingList = new ArrayList<Building>();
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        int 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());
            buildingList.add(new Building(lx, h));
            buildingList.add(new Building(rx, -h));
        }
 
        Collections.sort(buildingList, 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> tm = new TreeMap<Integer, Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
 
        List<Building> ansList = new ArrayList<Building>();
        for (int i = 0; i < buildingList.size(); i++) {
            Building cur = buildingList.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();
    }
}