접근 방법
알고리즘 : 스택
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;
}
'코딩테스트(알고리즘) > baekjoon' 카테고리의 다른 글
[baekjoon] 균형잡힌 세상 4949 (Javascript, c++) (0) | 2022.06.16 |
---|---|
[baekjoon] AC 5430 (C++) (0) | 2022.06.16 |
[baekjoon] 옥상 정원 꾸미기 6198 (Javascript, c++) (0) | 2022.06.15 |
[baekjoon] 탑 2493 (Javascript,c++) (0) | 2022.06.15 |
[baekjoon] 키로거 5397 (Javascript,c++) (0) | 2022.06.14 |