알고리즘 기초 1/2. 200 - 자료 구조 1
1874번. 스택 수열

문제

1874번 문제 링크

solution

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n").map((item) => Number(item));

const iter = input.shift();

// 답을 담기 위한 배열
let ans = [];

// 스택 생성
let stack = [];

// 스택은 1부터 차례대로만 넣을 수 있기 때문에 1을 시작 숫자로 지정한다.
let stackNum = 1;

for(let i = 0; i < iter; i++){
    // input의 배열값 순서대로 수열을 만들어야하므로
    // 우리가 stack에서 꺼내야할 숫자는 input[i]에 해당하는 숫자이다.
    let num = input[i];
    
    // stack에 stackNum을 push한다.
    // stackNum은 1부터 num까지 증가한다.
    // push할 때마다 ans 배열에 "+" 문자를 push한다.
    // 주의할 점. stackNum은 반복문 외부에 선언되었기 때문에
    // 반복문이 돌아갈 때 다시 1부터 시작될 일은 없다.
    // 즉, 순서대로 증가하면서 push 되는 것이 구현된 것이다.
    while(stackNum <= num){
        stack.push(stackNum);
        stackNum++;
        ans.push("+");
    }
    
    // stack에 num까지 들어갔으므로
    // pop을 하면 num과 같은 숫자가 나오게 된다.
    // pop할 때마다 ans 배열에 "-" 문자를 push한다.
    let stackPop = stack.pop();
    ans.push("-");
    
    // 만약 stack에서 pop한 값과 num이 일치하지않는다면
    // 그 것은 문제 조건에 맞춰서 수열로 만들어낼 수 없는 경우이므로
    // ans 배열을 ["NO"]로 완전히 교체하고, for문을 종료한다.
    if(stackPop !== num){
        ans = ["NO"];
        break;
    }   
}

console.log(ans.join("\n"));

이번 문제는 stack에 저장하는 것을 어떻게 구현할지 고민하다가 결국 다른 분이 풀이를 참고했다.

예시 데이터로 설명하는게 좋을 것 같다.

입력 데이터
8
4
3
6
8
7
5
2
1

가장 처음 주어진 숫자, 8은 수열의 길이이다.(iter)
4부터 1까지는 input 배열이 될 것이다. 이는 문제에서 말하는 수열을 의미한다.

빈 stack을 만들어주고, stack에는 1부터 8까지 차례대로 들어갈 수 있다.

여기서, 문제를 이해하고 넘어가야한다.
input은 [4,3,6,8,7,5,2,1] 이다. 이는 우리가 만들어내야할 수열이기도 하다.
그리고 우리는 stack에 1,2,3,...,8까지 순서대로 넣어줄 수 있고,
LIFO(Last In First Out) 구조인 스택에서는 나중에 들어간 것부터 꺼낼 수 있다.

수열을 만들기 위해서는 stack에 들어갔다가 나오는 숫자만 사용할 수 있다는 점을 잊지말자.

즉, input의 순서대로 수열을 만들어내기 위해서 stack을 조작해야한다는 뜻이다.

for문으로 들어가보자.
처음으로 해야할 것은 꺼내야할 숫자를 정하는 것이다.
꺼내줘야할 숫자는 input[i]이다.
여기서는 4를 가장 먼저 꺼내줘야하므로, num을 4로 설정한다.

stackNum를 1부터 시작해서 num까지 증가시키며 stack에 넣어준다.
이 때 ans 배열에는 "+" 문자를 넣어줘야한다.

현재 stack은 [1,2,3,4] 이다.

num까지 넣어줬으니, stack에서 pop을 하면 그 값은 num가 일치한다.
따라서, pop을 실행하고 ans에 "-" 문자를 넣어준다.

이제 for문 i가 증가한다.
이번에는 num이 3이다.

여기서 주의해야할 점은, stackNum은 for문 밖에 선언했기 때문에 다시 1로 돌아가지 않는다는 것이다.
따라서, while문의 조건을 불만족. 실행되지 않고 pop으로 넘어간다.

이렇게 반복하면서 수열을 만들어간다.

참고 자료

참고 자료 1