[baekjoon] 오큰수 17298 (Javascript,c++)

17298번: 오큰수 (acmicpc.net)

17298번: 오큰수

---

접근 방법

알고리즘 : 스택

 

1. 입력값을 별도의 배열에 정리

2. 끝부분 부터 값을 비교하며 스택에 추가, 비교

 

하루 종일 스택만 공부했더니 드디어 문제가 풀리기 시작했다.

아무것도 참고하지 않고 스스로 문제를 풀었고 정답을 맞혔다.

 

더 좋은 풀이를 위해 정답 코드를 확인했는데 거의 같은 방법으로 구현했다.

---

Javascript

/**
 * 제출용. 아래 로컬용을 지우고 제출하자.
 */
//  let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n")
/**
 * 로컬용, 예제.txt를 생성해서 예제를 복붙하자.
 */
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 stk = [];
  let ans = [];

  for (let i = n; i > 0; i--) {
    let tmp = arr[i - 1];
    arr.pop();

    if (stk.length === 0) {
      ans.push(-1);
      stk.push(tmp);
    } else {
      while (stk.length !== 0 && stk[stk.length - 1] <= tmp) {
        stk.pop();
      }
      if (stk.length === 0) {
        ans.push(-1);
        stk.push(tmp);
      } else {
        let stkTmp = stk[stk.length - 1];
        ans.push(stkTmp);
        stk.push(tmp);
      }
    }
  }

  ans.reverse();

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

solution();

 

---

C++

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

int a[1000000];
int ans[1000000];

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

  int n;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  stack<int> S;
  for (int i = n - 1; i >= 0; i--) {
    while (!S.empty() && S.top() <= a[i]) S.pop();
    if (S.empty())
      ans[i] = -1;
    else
      ans[i] = S.top();
    S.push(a[i]);
  }
  for (int i = 0; i < n; i++) cout << ans[i] << ' ';



  return 0;
}