[baekjoon] 옥상 정원 꾸미기 6198 (Javascript, c++)

6198번: 옥상 정원 꾸미기 (acmicpc.net)

6198번: 옥상 정원 꾸미기

---

접근 방법

알고리즘 : 스택

 

1. 입력 값을 stack에 넣어주며 현재 나의 값보다 큰 값의 수를 더해준다.

 

문제 구현은 쉬웠으나 문제에 접근하는 방법이 어렵다.

다양한 문제를 풀면서 접근 방법에 익숙해져야겠다.

 

// 평소 javascript splice를 통해 입력값을 정리하는데 시간 초과가 발생했다.

앞으로는 입력값 정리를 조금 더 신경 써서 최적화해야겠다.

---

Javascript

function solution() {
  let input = require("fs")
    .readFileSync("input.txt") //"/dev/stdin"
    .toString()
    .trim()
    .split("\n")
    .map((val) => val.trim());

  let n = +input[0];
  let cnt = 0;
  let tower = [];
  for (let i = 1; i <= n; i++) {
    let h = +input[i];

    while (tower.length != 0 && tower[tower.length - 1] <= h) {
      tower.pop();
    }
    cnt += tower.length;
    tower.push(h);
  }

  console.log(cnt);
}

solution();

 

---

C++

#include <bits/stdc++.h>
using namespace std;

#define ll long long

stack<int> s;
int n;
ll ans;

int main() {
  freopen("input.txt", "r", stdin); //제출 시 삭제
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  ll h;
  while (n--) {
    cin >> h;
    while(!s.empty() && s.top() <= h)
      s.pop();
    ans += s.size();
    s.push(h);
  }
  cout << ans;
  return 0;
}