[baekjoon] 탑 2493 (Javascript,c++)

2493번: 탑 (acmicpc.net)

2493번: 탑

---

접근 방법

알고리즘 : 스택

 

c++ stack으로 무식하게 구현했더니 시간초과 발생.

바킹독 님의 풀이를 참고하여 Javascipt로 직접 문제풀이 완료.

 

---

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 arr = input[1].split(" ").map((v) => +v);
  let tower = [[100000001, 0]];
  let ans = [];

  for (let i = 1; i <= n; i++) {
    while (tower[tower.length - 1][0] < arr[i - 1]) {
      tower.pop();
    }

    ans.push(tower[tower.length - 1][1]);
    tower.push([arr[i - 1], i]);
  }

  console.log(ans.join(" "));
}

solution();

 

---

C++

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int N;
stack<pair<int,int>> tower;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> N;  
  tower.push({100000001, 0});
  for (int i = 1; i <= N; i++) {
    int height;
    cin >> height;
    while (tower.top().X < height)
      tower.pop();    
    cout << tower.top().Y << " ";
    tower.push({height, i});      
  }
}