[백준/JavaScript] 스카이라인 쉬운거(1863)

문제

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

도시에서 태양이 질 때에 보이는 건물들의 윤곽을 스카이라인이라고 한다. 스카이라인만을 보고서 도시에 세워진 건물이 몇 채인지 알아 낼 수 있을까? 건물은 모두 직사각형 모양으로 밋밋하게 생겼다고 가정한다.

정확히 건물이 몇 개 있는지 알아내는 것은 대부분의 경우에 불가능하고, 건물이 최소한 몇 채 인지 알아내는 것은 가능해 보인다. 이를 알아내는 프로그램을 작성해 보자.

 

[입력]

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 번째 지점의 x좌표는 항상 1이다.

 

[출력]

첫 줄에 최소 건물 개수를 출력한다.

 

풀이

// 백준 - 스카이라인 쉬운거(1863)
const solution = ( input ) => {
  const N = parseInt(input.shift());
  let skylines = input.map((o) => o.split(" ").map((p) => parseInt(p)));

  // x좌표를 기준으로 오름차순 정렬
  skylines.sort((o1, o2) => o1[0] - o2[0]);

  let answer = 0;
  const stack = [];

  for(let i = 0; i < skylines.length; i++) {
    // 스택에 쌓인 값 = 제일 가까운 건물의 높이가 현재 체크 중인 건물의 높이보다 높은 경우
    // 해당 높이의 건물이 무조건 있는 것이므로 카운트
    while(stack[stack.length - 1] > skylines[i][1]) {
      answer++;
      stack.pop();
    }

    // 스택이 비어있거나, 가장 가까운 건물의 높이보다 낮으면 스택에 쌓기
    if(skylines[i][1] > 0 && (stack.length == 0 || stack[stack.length - 1] < skylines[i][1])) {
      stack.push(skylines[i][1]);
    }
  }

  // 남은 거
  answer += stack.length;

  console.log(answer);
}

/*
테스트용: __dirname + '/input.txt'
제출용: '/dev/stdin'
*/
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

solution(input);