leetcode 218. The Skyline Problem

🍀 문제

https://leetcode.com/problems/the-skyline-problem/

The Skyline Problem - LeetCode

 

 

🍀 나의 코드

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<List<Integer>> answer = new ArrayList<List<Integer>>();
		List<int[]> height = new ArrayList<int[]>(); // x좌표와 높이 저장
		for(int i=0; i<buildings.length; i++) {
			height.add(new int[] {buildings[i][0],buildings[i][2]}); // startX , height
			height.add(new int[] {buildings[i][1],-buildings[i][2]});// endX , -height
		}
		
		// x좌표를 기준으로 오름차순 / x좌표가 같다면 높이가 큰 순으로 정렬
		Collections.sort(height,(o1,o2)->{
			if(o1[0] > o2[0]) return 1;
			else if(o1[0] == o2[0] && o1[1] < o2[1]) return 1;
			else return -1;
		});
		
		int nowHeight = 0; //현재 높이
		PriorityQueue<Integer> q = new PriorityQueue(Collections.reverseOrder()); // 현재 위치의 빌딩높이 저장(내림차순으로 정렬)
		q.add(0);
		for(int i=0; i<height.size(); i++) {
			if(height.get(i)[1] < 0) { // -height이면 q에서 제거
				q.remove(-height.get(i)[1]);
			}else {// 아니면 q에 추가
				q.add(height.get(i)[1]);
			}
			
			if(nowHeight != q.peek()) { // 제일 높은 높이와 현재 높이가 다르다면 answer에 추가
				nowHeight = q.peek();
				List<Integer> list = new ArrayList(Arrays.asList(height.get(i)[0],nowHeight));
				answer.add(list);
			}
		}
		
		return answer;
    }
}