[백준] 1863 - 스카이라인 쉬운거 (node.js)

문제

 

코드

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");

input.shift();
const data = input.map((value) => +value.split(" ")[1]);

// 높이가 줄어들때마다 pop() 하면서 count 올려줌 -> stack의 맨 위의 값이 햔재 값보다 작을때까지
// 현재 높이가 0보다 크고, stack이 비어있거나, stack의 맨 위의 값보다 현재 값이 클 때 push()
// 배열을 다 돌았는데 stack에 값이 남아있다면 남아있는 만큼 count 늘려줌
// 높이가 같다면 같은 건물일 수도 있기 때문에 push 안함

let stack = [];
let count = 0;

data.map((v) => {
  while (stack.length !== 0 && v < stack[stack.length - 1]) {
    stack.pop();
    count++;
  }

  if (v > 0 && (stack.length === 0 || v > stack[stack.length - 1])) {
    stack.push(v);
  }
});

console.log(count + stack.length);

 

문제 해결 과정

 

솔직히 문제를 딱 보고 어떻게 풀어야 할지 감도 안 왔다. 원래 같았으면 2시간 정도 고민해 보고 바로 풀이 방법을 봤을 텐데 오랜만에 제대로 된 알고리즘을 푼다는 생각에 몇 날 며칠을 고민했던 것 같다. (결국엔 봤음 ㅜ.ㅜ)

그래도 높이가 낮아질 때를 캐치해야겠구나!라는 생각은 하고 있었어서 stack을 사용해야 한다는 풀이를 보고 나서는 별 어려움 없이 풀었던 것 같다. 근데 틀렸다..!

 

해결 방법

1. 높이가 줄어들때마다 pop() 하면서 count 올려줌 -> stack의 맨 위의 값이 현재 값보다 작을 때까지
2. 현재 높이가 0보다 크고, stack이 비어있거나, stack의 맨 위의 값보다 현재 값이 클 때 push()
3. 배열을 다 돌았는데 stack에 값이 남아있다면 남아있는 만큼 count 늘려줌
4. 높이가 같다면 같은 건물일 수도 있기 때문에 push 안 함

 

현재 높이(v)보다 stack 최상단의 값이 작다면 건물이 끝나는 시점일 것이라고 생각했다. 그리고 값이 같다면 같은 건물일 것이라고 생각해서 stack에 추가해주지 않았다.

시간복잡도

입력받은 만큼 반복문을 실행해야 하기 때문에 O(n)이다.

그리고 반복문을 돌면서 push(), pop()을 모두 하게 된다면 O(1), O(1) 이기 때문에 전체 시간 복잡도는 O(n)이다.

 

문제점

stack.pop()과 stack.push()의 조건 문제

이전에는 현재 높이가 stack의 맨 위의 값이랑 같을 때도 pop()을 수행했었는데 이러다 보니 count값이 결과보다 더 많이 나왔었다. 그리고 현재 높이가 0일 때도 push()를 해줬었는데 이 부분도 조건을 걸어 잡아주었다.

 

느낀 점

 

결국 풀이 방법을 봤다는 점이 너무 아쉬웠다.. 뭐 시간은 많으니까!! 열심히 노력해 볼 의지가 생겼다!!

 

그리고 거의 처음으로 시간 복잡도, 공간 복잡도를 계산해 봤던 것 같다. 이전에는 자바로만 알고리즘을 풀었어서 데이터 타입이 다른 자바스크립트는 공간 복잡도를 어떻게 계산해야 할지 전혀 몰랐다. 그래서 찾아보니 자바스크립트는 동적 타입 시스템으로 인해 메모리 사용량이 실행시마다 달라질 수 있고, 가비지 컬렉션이라는 것을 통해 자동으로 메모리를 관리한다고 한다.

결론! 자바스크립트로 알골 풀 때는 시간 복잡도를 우선으로 고려해 봐야겠다.

 

백준에서는 자바스크립트로 알고리즘을 풀려면 node.js를 사용해야 했다.

오.. 입력부터 난관이었다. 그래서 vscode에서 예제 입력을 txt로 만들어서 풀었다.

 

정말 자바스크립트 알고리즘 쉽지 않다!