[boj] 1874. 스택 수열

[boj] 1874. 스택 수열

• 문제 링크 : https://www.acmicpc.net/problem/1874
• 사용 언어 : Node.js

1874번: 스택 수열

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push 하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

---

1. 문제 분석

이 문제는 위에 기술되어 있듯이 Stack을 활용하는 문제입니다.
수를 입력받고 발생할 수 있는 상황은 세 가지로 나눌 수 있습니다. 현재까지 push 한 최댓값보다 입력 값이 큰 경우, 같은 경우, 작은 경우입니다.

 1. 입력 값이 최대값보다 큰 경우 입력 값에 도달할 때까지 순차적으로 Stack에 값을 push 하고 도달한 후  pop을 해주면 됩니다.

 2. 입력 값이 최대값과 같은 경우는 1번의 시나리오에서 오름차순으로 push를 진행하며 원하는 수에 도달하였을 때 pop 하므로 발생하지 않는 시나리오입니다.

3. 주의해야 할 경우는 최댓값보다 작은 수가 나오는 경우입니다.
풀이의 실마리는 "Stack에 push 하는 순서는 반드시 오름차순"이라는 문장입니다. 이 문장이 뜻하는 바는 Pop을 통해 출력할 수 있는 수는 오직 현재 Stack 안에 있는 수들 중 최댓값인 Top에 위치해 있는 수 한 가지뿐이라는 것입니다. 현재 Top에 위치해 있는 이 외의 수를 입력받게 되면 만들어 낼 수 없는 수열입니다. 이때에는 "NO"를 출력하고 종료합니다.

이제 코드를 보며 확인해 보겠습니다.

 

---

2. 솔루션

const fs = require('fs');
const input = fs.readFileSync(process.platform ===
                              'linux' ? '/dev/stdin' : 'input.txt').toString()
                .split('\n').map(n => +n);
const [N, ...numbers] = input;
// 연산
let operations = [];
// 오름차 순 Stack
const stack = [];
// Stack에 push 되었던 수들 중 최대값
let current = 0;

for (let i = 0; i < N; i++) {
    // 출력 되어야 하는 수열 내의 수
    const numberOfSequence = numbers[i];
    // 출력해야할 수가 Stack에 push 되었던 수보다 큰 경우
    if (current < numberOfSequence) {
        // 해당 수에 도달할 때까지 수를 Stack에 push
        while (current < numberOfSequence) {
            stack.push(++current);
            operations.push('+');
        }
        // 해당 수에 도달 후 pop하여 출력
        stack.pop();
        operations.push('-')
    } else {
        // Stack의 Top이 입력된 수와 일치하는 경우 true
        let found = false;
        if (stack.length !== 0) {
            const top = stack[stack.length - 1];
            if (top === numberOfSequence) {
                stack.pop();
                operations.push('-')
                found = true;
            }
        }
        if(!found) {
            operations = ["NO"];
            break;
        }
    }
}

console.log(operations.join('\n'))

마치며

 문제를 처음 읽었을 때 이해하는 데에 어려움을 겪었습니다. 하여 다른 분들의 문제 해석을 여러 번 읽고 제 것으로 만들었습니다. 이 문제의 핵심은 오름차순이라는 조건을 통해 Stack이라는 하나의 공간만을 사용하도록 제약했다는 것입니다.
 또 저는 Node.js로 풀이할 때 입력을 한 번에 읽어 사용합니다. 하지만 이 문제를 풀면서 때로는 한 번에 입력을 읽는 것이 아닌 "한 줄씩 입력이 들어왔을 때는 어떻게 풀이할까?" 생각해 보는 것이 문제를 이해할 때 도움이 되는 경우가 존재한다 느낄 수 있는 문제였습니다.