[JavaScript/Stack] 백준 실버 2 : 1874 - 스택 수열

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

---

📌 작성한 코드 1 

// 1874
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Silver/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n").map(Number);

const N = Number(input.shift());
const targets = input.map(Number);

const before = Array.from({ length: N }, (_, i) => i + 1).reverse();
const after = [];
let visited = new Array(N + 1).fill(false);

const commands = [];

let flag = true;

for (const num of targets) {
    while (!visited[num]) {
        const temp = before.pop();
        after.push(temp);
        commands.push("+");
        visited[temp] = true;
    }

    if (visited[num]) {
        const temp = after.pop();
        if (temp !== num) {
            flag = false;
            break;
        } else {
            commands.push("-");
        }
    }
}

console.log(flag ? commands.join("\n") : "NO");

 

 

📌 풀이 

1~N까지의 숫자가 있는데 이를 차례대로 push나 pop했을 때 입력받은 순서대로 나열할 수 있는지 묻는 문제이다. 

stack에 숫자들을 차례로(1~N) push할건데 이 때 pop해서 숫자를 꺼내 출력할 수 있다.

 

before : 1부터 N까지의 숫자가 차례대로 들어있는 배열(pop을 위해서 반대로 넣어놨음)

after : 현재까지 push해서 저장한 숫자가 들어있는 배열

visited : 현재 이 숫자가 나온적이 있는지 확인하는 배열(after에 들어가 있는지, indexOf로 찾아도 되지만 시간 줄이기 위해 사용)

for (const num of targets) {
    while (!visited[num]) { // 현재 1~N까지의 숫자를 차례로 꺼내서 넣고 있는데 확인한 적 없는 경우
        const temp = before.pop(); // 숫자 꺼내서 
        after.push(temp); // after에 넣음
        commands.push("+"); // 꺼내서 넣었으니까 push 표시
        visited[temp] = true; // 이제 해당 숫자가 나왔음을 기억하기 
    }

    if (visited[num]) { // 숫자가 나온적이 있음 == after에 존재함
        const temp = after.pop(); // 출력하기 위해서 꺼냄
        if (temp !== num) { // 꺼낸 숫자가 내가 원하는 num이 맞는지 확인
            flag = false; // 일치하지 않으면 우리는 입력이 원하는 수열을 만들 수 없으므로 불가능 표시
            break;
        } else {
            commands.push("-"); // 원하는 숫자가 맞으면 pop 기록하기
        }
    }
}

 

 

bfs에 익숙해져서 방문 배열 사용했는데 사실 숫자를 순서대로 돌고 있어서 필요없고 숫자 비교를 통해서 구할 수 있다. 그래서 작성한 다음 버전이다.

---

📌 작성한 코드 2

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Silver/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n").map(Number);

const N = Number(input.shift());
const targets = input.map(Number);

let current = 1;
const stack = [];
const commands = [];
let flag = true;

for (const num of targets) {
    while (num >= current) {
        stack.push(current++);
        commands.push("+");
    }

    const popped = stack.pop();
    commands.push("-");

    if (popped !== num) {
        flag = false;
        break;
    }
}

console.log(flag ? commands.join("\n") : "NO");

 

현재까지 확인한 숫자가 내가 찾고자 하는 num보다 작은 경우 계속해서 숫자를 증가시키면서 num이 될 때까지 stack에 추가한다. 

그리고 stack에 원하는 숫자가 있는 경우 stack 맨 위의 숫자가 내가 원하는 숫자인지 확인한다. 

---

✅ 성공