[백준 1874] 스택 수열
February 12, 2023
문제
https://www.acmicpc.net/problem/1874
아이디어
- 입력 값을 정제해서 만들어야 할 수열 정보를 배열로 저장한다.
-
1부터 n까지 증가시키며 다음과 같은 로직을 수행한다.
- 현재 숫자를 스택에 넣고 +연산을 한다.
- 만약 다음에 와야 할 값이 현재 숫자보다 작거나 같다면 이미 스택에 있다는 것이므로 스택에 더 큰 값이 남아있을 때까지 빼고 -연산을 한다. 이때, 스택에서 꺼낸 값이 다음에 와야 할 값과 일치하지 않는다면 만들 수 없는 수열이 되므로 NO를 출력하고 종료한다.
- 수행했던 스택 연산의 과정을 출력한다.
소스코드
// 입력 정제
const INPUT_NAME = "i1.txt";
const filePath = process.platform === "linux" ? "/dev/stdin" : `./${__dirname.split('\\').pop()}/${INPUT_NAME}`;
const input = require("fs").readFileSync(filePath).toString().trim().split("\n").map(item => item.trim());
const n = Number(input[0]);
const arr = [];
for (let i = 1; i <= n; i++) {
arr.push(Number(input[i]));
}
// 문제
function solution() {
const stack = [];
const result = [];
let cursor = 0;
// 1부터 n까지 스택에 넣으면서 진행
for (let i = 1; i <= n; i++) {
stack.push(i);
result.push("+");
// 다음으로 와야 할 값이 스택에 들어왔으면 다음으로 와야 할 값이 스택의 끝에 없을 때까지 꺼냄
if (i === arr[cursor]) {
while (i >= arr[cursor]) {
// 만약 스택에서 꺼낸 값이 다음으로 와야 할 값과 일치하지 않는다면, 만들 수 없는 수열이므로 NO를 출력하고 종료
if (stack.pop() !== arr[cursor]) {
console.log("NO");
return;
}
result.push("-");
cursor++;
}
}
}
console.log(result.join("\n"));
}
// 실행
solution();