문제
N개의 직사각형 건물(왼쪽 x, 높이, 오른쪽 x)이 주어졌을 때, 건물들의 스카이라인 윤곽선을 구하라. 높이가 변하는 지점의 (x, 높이) 쌍을 출력한다.
입력
첫째 줄에 N, 이후 N개의 줄에 각 건물의 왼쪽 x, 높이, 오른쪽 x가 주어진다.
출력
스카이라인의 꼭짓점을 왼쪽부터 순서대로 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 2 2 4 3 4 6 | 2 2 3 4 6 0 |
풀이
이벤트 기반 스위핑과 TreeMap으로 현재 최대 높이를 추적한다.
- 각 건물의 왼쪽 끝을 양수 높이, 오른쪽 끝을 음수 높이로 이벤트 리스트에 추가한다
- 이벤트를 x 좌표순으로 정렬한다 (같은 x면 높이 내림차순)
TreeMap(내림차순)으로 현재 활성 건물의 높이를 관리한다- 양수 높이 이벤트: TreeMap에 추가. 음수 높이 이벤트: TreeMap에서 제거
- 이벤트 처리 후 최대 높이(
firstKey)가 이전과 다르면 스카이라인 꼭짓점으로 추가한다
핵심 아이디어: 건물의 시작과 끝을 이벤트로 분리하고, TreeMap으로 현재 보이는 최대 높이를 O(log N)에 관리한다. 높이 변화가 있을 때만 출력한다.
코드
package day349;
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 Day345BOJ1933스카이라인 {
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();
}
}복잡도
- 시간: O(N log N)
- 공간: O(N)