[백준] 6198

옥상 정원 꾸미기

문제

도시에는 N개의 빌딩이 있다.

빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다.

i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.

i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.

그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.

예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우

             = 
 =           = 
 =     -     = 
 =     =     =        -> 관리인이 보는 방향
 =  -  =  =  =   
 =  =  =  =  =  = 
10  3  7  4  12 2     -> 빌딩의 높이
[1][2][3][4][5][6]    -> 빌딩의 번호

• 1번 관리인은 2, 3, 4번 빌딩의 옥상을 확인할 수 있다.
• 2번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 3번 관리인은 4번 빌딩의 옥상을 확인할 수 있다.
• 4번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 5번 관리인은 6번 빌딩의 옥상을 확인할 수 있다.
• 6번 관리인은 마지막이므로 다른 빌딩의 옥상을 확인할 수 없다.

따라서, 관리인들이 옥상정원을 확인할 수 있는 총 수는 3 + 0 + 1 + 0 + 1 + 0 = 5이다.

입력

• 첫 번째 줄에 빌딩의 개수 N이 입력된다.(1 ≤ N ≤ 80,000)
• 두 번째 줄 부터 N+1번째 줄까지 각 빌딩의 높이가 h 입력된다. (1 ≤ h ≤ 1,000,000,000)

출력

• 각 관리인들이 벤치마킹이 가능한 빌딩의 수의 합을 출력한다.

풀이

const roofPark = () => {
  const fs = require("fs");
  let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
  const len = parseInt(input[0]);
  let stack = [];
  let sum = 0;
  input.shift();
  input.reverse();
  input = input.map((n) => {
    return parseInt(n);
  });

  for (let i = len - 1; i >= 0; i--) {
    while (stack.length > 0 && stack[stack.length - 1] <= input[i]) {
      stack.pop();
    }
    sum += stack.length;
    stack.push(input[i]);
  }
  console.log(sum);
};

roofPark();

반성회

각각의 관리자가 볼 수 있는 빌딩의 개수를 세지 않고, 각각의 빌딩마다 이를 볼 수 있는 관리자의 명수를 센다

// ======= 입력값 =======
6
10
3
7
4
12
2

입력값 배열: [2, 12, 4, 7, 3, 10]
// 맨 왼 쪽에 있는 빌딩부터 검사하므로 배열의 순서를 뒤집어주었다

// ======= 동작 =======
0번째 루프
현재 원소: 10
스택: []
// 스택이 비어 있으므로 아무것도 pop하지 않는다
// 높이가 10인 빌딩을 볼 수 있는 관리자는 아무도 없다
빌딩 개수의 합: 0

1번째 루프
현재 원소: 3
스택: [10]
// 스택이 비어있지 않지만, 10은 3보다 크므로 아무것도 pop하지 않는다
// 높이가 3인 빌딩을 볼 수 있는 관리자는 높이가 10인 빌딩에 있는 관리자 한 명 뿐
// 따라서 임의의 관리자가 볼 수 있는 빌딩의 수가 1 늘어난다
빌딩 개수의 합: 1

2번째 루프
현재 원소: 7
스택: [10, 3]
// 스택이 비어있지 않고, 7은 3보다 크므로 3을 pop한다
// 높이가 7인 빌딩을 볼 수 있는 관리자는 높이가 10인 빌딩에 있는 관리자 한 명 뿐
// 따라서 임의의 관리자가 볼 수 있는 빌딩의 수가 1 늘어난다
빌딩 개수의 합: 2

3번째 루프
현재 원소: 4
스택: [10, 7]
// 스택이 비어있지 않지만, 7은 4보다 크므로 아무것도 pop하지 않는다
// 높이가 4인 빌딩을 볼 수 있는 관리자는 높이가 10인 빌딩과 높이가 7인 빌딩의 관리자 두 명
// 따라서 임의의 관리자가 볼 수 있는 빌딩의 수가 2 늘어난다
빌딩 개수의 합: 4

4번째 루프
현재 원소: 12
스택: [10, 7, 4]
// 스택이 비어있지 않고 4, 7, 10 모두 12보다 작으므로 pop을 3번 진행한다
// 높이가 12인 빌딩을 볼 수 있는 관리자는 아무도 없다 (스택이 비었으므로)
빌딩 개수의 합: 4

5번째 루프
현재 원소: 2
스택: [12]
// 스택이 비어있지 않고 12는 2보다 크므로 아무것도 pop하지 않는다
// 높이가 2인 빌딩을 볼 수 있는 관리자는 높이가 12인 빌당의 관리자 한 명 뿐
// 따라서 임의의 관리자가 볼 수 있는 빌딩의 수가 1 늘어난다
빌딩 개수의 합: 5

// ====== 출력 =======
5