[백준] 1933번 스카이라인 Java

문제 링크

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

문제

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좌표와 그 지점에서의 높이를 출력한다.

알고리즘: 우선순위 큐

풀이

각 건물의 왼쪽 x값이 작은 값을 우선으로 하는 우선순위 큐를 선언한다.
현재 좌표에서 가장 높은 빌딩을 h_b라 하고 새로운 빌딩을 nb라고 하겠다.
h_b의 h값이 nb의 h값보다 크다면 h_b와 nb의 차집합 부분을 우선순위 큐에 넣어준다.
h_b의 h값이 nb의 h값보다 작다면 h_b를 nb의 값으로 업데이트해 주고 기존 h_b값과 NB의 값의 차집합 부분이 h_b를 기준으로 뒤에 존재하는 영역은 ans_list에 넣어주고, h_b를 기준으로 앞에 존재하는 영역은 우선순위 큐에 넣어준다.
위 방식은 h_b.l <= nb.l < h_b.r 일 때 반복해주고 -> 교집합 부분이 존재할 때
교집합 부분이 존재하지 않으면 h_b를 n_b로 업데이트해 주고 h_b값은 ans_list에 넣어준다. 여기서 주의할 점은 h_b.l과 n_b의 r이 같으면서 h값도 같다면 h_b.r을 n_b의 r로 업데이트만 해줘야 한다. **(동일한 높이의 빌딩이 끊어지지 않고 연결되기 위해서)

소스 코드

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

class Building implements Comparable<Building>{
    long l ,h, r;
    public Building(long l, long h, long r) {
        this.l = l;
        this.h = h;
        this.r = r;
    }
    
    public int compareTo(Building n) {
        long dif = this.l - n.l;
        if(dif > 0) return 1;
        else if(dif < 0) return -1;
        else return 0;
    }
}

public class Main {
    static int N;
    static PriorityQueue<Building> pq = new PriorityQueue<>();
    static Building hest_building;
    static ArrayList<Building> ans = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      for(int i=0; i<N; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          pq.add(new Building(Long.parseLong(st.nextToken()), Long.parseLong(st.nextToken()), Long.parseLong(st.nextToken())));
      }
      hest_building = pq.poll();
      while(pq.size() != 0) {
          Building nb = pq.poll();
          if((hest_building.l <= nb.l) && (hest_building.r > nb.l)) {
              if(hest_building.h >= nb.h) {
                  if(hest_building.r < nb.r) {
                      pq.add(new Building(hest_building.r, nb.h, nb.r));
                  }
              } else {
                  if(hest_building.l == nb.l) {
                      if(hest_building.r > nb.r) {
                          pq.add(new Building(nb.r, hest_building.h, hest_building.r));
                      }
                  } else {
                      if(hest_building.r > nb.r) {
                          pq.add(new Building(nb.r, hest_building.h, hest_building.r));
                      }
                      ans.add(new Building(hest_building.l, hest_building.h, nb.l));
                  }
                  hest_building = nb;
              }
          } else if(hest_building.r == nb.l && hest_building.h == nb.h){
              hest_building.r = nb.r;
          } else {
              ans.add(hest_building);
              hest_building = nb;
          }
      }
      ans.add(hest_building);
      for(int i=0; i<ans.size(); i++) {
          str_append(ans.get(i).l, ans.get(i).h);
          if(i != ans.size() - 1) {
              if(ans.get(i).r != ans.get(i+1).l) str_append(ans.get(i).r, 0);
          } else {
              str_append(ans.get(i).r, 0);
          }
      }
      System.out.println(sb.toString());
    }
    
    static void str_append(long x, long h) {
        sb.append(x);
        sb.append(" ");
        sb.append(h);
        sb.append(" ");
    }
}