[LeetCode] 218. The Skyline Problem [JAVA(자바)]

'기술면접 라이브코딩 - 승지니어'를 보고 작성한 글입니다. 😀

문제 👉 <The Skyline Problem - LeetCode>

1. 문제

빌딩의 좌표가 주어졌을 때, 모든 빌딩이 형성하는 실루엣의 바깥 쪽 윤곽점을 나타내어라.

Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]

2. 풀이

Sort 와 TreeMap 을 이용한 풀이

빌딩을 2개의 Line으로 나눈다.

• 빌딩의 왼쪽과 오른쪽을 구분하기 위해 왼쪽은 높이에 마이너스를 붙인다. (-height)

  • (left, -height), (right, height)

  • List<Line> lines = new ArrayList<>(buildings.length* 2);
    for (int[] b : buildings) {
        lines.add(new Line(b[0], -b[2]));
        lines.add(new Line(b[1], b[2]));
    }

Sort 를 통해 빌딩의 Line을 x축은 오름차순으로, x값이 같다면 y값(hegiht)을 오름차순으로 정렬한다.

• Collections.sort(lines, (l1, l2) -> {
      int compX = Integer.compare(l1.x, l2.x);    // x축 오름차순
      if (compX != 0) return compX;   // x축이 같지않을 때 
      return Integer.compare(l1.y, l2.y); // x축이 같다면 y축 오름차순
  });

TreeMap 을 통해 현재 빌딩의 최대 높이를 확인하고 윤곽선을 찍는다.

• TreeMap 의 key 값을 높이로 하여 lastKey() 를 통해 최대 높이를 찾는다.

• 추가되는 빌딩의 높이가 현재 TreeMap 의 최대 높이 보다 크다면 윤곽선을 찍는다.

  • 추가되는 빌딩이 2개이고 높이가 다르다면 높이가 큰 것 부터 TreeMap에 추가하여 윤곽선을 찍는다.

  • 

  • 제거되는 빌딩이 2개이고 높이가 다르다면 높이가 작은 것 부터 TreeMap에서 제거하여 윤곽선을 하나만 찍는다.

  • 

3. 코드

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        if (buildings == null || buildings.length == 0) return new ArrayList<>();

        List<List<Integer>> ret = new ArrayList<>();
        List<Line> lines = buildinglines(buildings);

        // <빌딩 높이, 같은 높이의 빌딩 개수>
        TreeMap<Integer, Integer> map = new TreeMap<>();
        map.put(0, 1);    // 빌딩의 마지막을 위해 미리 넣음
        int prev = 0;

        for (Line line : lines) {
            if (line.y < 0) {   // 빌딩의 왼쪽(시작점)
                map.put(-line.y, map.getOrDefault(-line.y, 0) + 1); // map에 추가
            } else {  // 빌딩의 오른쪽(종료점)
                int count = map.get(line.y);    // 같은 높이의 빌딩 개수
                if (count > 1) {
                    map.put(line.y, count-1);   // 카운트 -1
                } else { // If the line is the last coordinate left line, remove it.
                    map.remove(line.y);         // 같은 높이의 빌딩 없다면 map에서 제거
                }
            }

            int cur = map.lastKey(); // 현재 빌딩의 최대 높이

            // 빌딩의 최대 높이가 바뀌면 윤곽선을 찍는다.
            if (cur != prev) {  
                ret.add(Arrays.asList(line.x, cur));
                prev = cur;
            }
        }

        return ret;
    }

    private List<Line> buildinglines(int[][] buildings) {
        // 빌딩 2개의 좌/우 라인으로 나누기
        List<Line> lines = new ArrayList<>(buildings.length* 2);
        for (int[] b : buildings) {
            lines.add(new Line(b[0], -b[2]));
            lines.add(new Line(b[1], b[2]));
        }

        // 정렬
        Collections.sort(lines, (l1, l2) -> {
            int compX = Integer.compare(l1.x, l2.x);    // x축 오름차순
            if (compX != 0) return compX;   // x축이 같지않을 때 
            return Integer.compare(l1.y, l2.y); // x축이 같다면 y축 오름차순
        });

        return lines;
    }

    class Line {
        int x, y;
        Line(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

• 결과 :

Time Submitted	Status	Runtime	Memory	Language
05/04/2021	Accepted	15 ms	41.7 MB	java

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋