백준 6198 < 옥상 정원 꾸미기 > JavaScript

📍문제 링크

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

6198번: 옥상 정원 꾸미기

 

📍알고리즘 분류

- 자료구조
- 스택
 

📍문제 풀이

문제 요구사항은 쉽지만, N이 최대 8만에 달하기 때문에, O(N^2) 로는 해결할 수 없다
- 시간복잡도를 낮추기 위한 방법이 필요하다
 
배열을 순회하며
 
stack 길이만큼 반복문 수행
스택의 최신 값이 현재값보다 같거나 작으면, pop 실행,
아니면(가려져서 안보이므로) 종료
 
반복문 종료후 스택의 길이를 답에 더한다
그리고 스택에 현재 값을 push한다
 
이 과정에서 현재값마다, 이전 수들이 현재값보다 높으면 그만큼 답에 더해준다
즉,

/*
10  3  7  4  12  2
   +1  +1 +2     +1
   10  10  7     12
           10
*/

 

📍코드 (JavaScript)

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const N = +input[0];
  const stack = [];
  let answer = 0;
  // 1부터 N까지 순회
  for (let i = 1; i < N + 1; i++) {
    while (stack.length > 0) {
    // 스택에 원소가 있고, 현재값이 스택 맨 위 값보다 크면, pop 실행을 반복
      if (stack[stack.length - 1] <= +input[i]) stack.pop();
      else break;
    }
    // 남은 스택 길이만큼 더하기
    answer += stack.length;
    // 스택에 현재값을 push
    stack.push(+input[i]);
  }
  console.log(answer);
});

 

📍리뷰

- Bigint를 사용하지 않아도 가능하다. 8만 * 8만 해도 64억이므로 커버 가능!
- number 원시값의 최대 (max integer)
2^53 - 1 : 약 900조