[백준_1874] 스택수열

문제

접근법



1. 최초 스택에 담을 개수인 N을 입력받는다.

 

문제에서 요구한 변수 이름인 'n'을 통해 입력 받을 변수의 개수를 입력받습니다.

 

2. 스택에 담을 값들을 입력받고, 오름차순으로 push한다.

 

- 입력받고 오름차순으로 push 하는 방법

 

스택에 담을 값들을 n번 루프하여 입력을 받는 것은 어렵지 않은데 이를 오름차순으로 입력받는 것이 어려움을 주었습니다.

 

저는 이러한 문제를 해결 하기 위해서, index라는 변수를 1로 설정하고 tmp라는 변수를 통해 스택에 담을 값을 각각 받아서 

 

만약 index가 tmp보다 작다면, 그 값들을 모두 스택에 담는 방법으로 문제를 해결 하였습니다.

 

- 왜 스택을 쓰는가?

 

스택은 FILO 의 구조로써 먼저 들어온 것이 나중에 나가는 구조를 가지고 있습니다.

 

문제에서 제시된 4, 3, 6, 8 과 같은 순서대로 입력을 받는다고 가정하고, 위와 같은 방법으로 입력을 받게 되면

 

첫 루프를 돌게 됬을 때 스택에는 [1,2,3,4] 의 값들이 있을겁니다. 실제로 우리가 입력받은 값은 '4'만 존재하고 [1,2,3] 값은 오름차순의 룰을 지키기 위해서 미리 삽입을 한 것 입니다. 

 

이 때, 스택을 쓰는 이유를 알 수 있으실건데, [1,2,3]은 미리 넣었지만 "나중에" 사용한다 즉, FILO의 구조를 가진 스택을 효과적으로 사용 할 수 있습니다.

 

 

3. pop을 통해 최초에 입력 받은 순서와 같은 수열을 만들어낸다.

 

스택의 사용이유에서 예시를 보면 최초 루프를 돌게 되면, 우리의 스택에는 [1,2,3,4]가 존재합니다.

 

우리의 목적은 입력받은 순서와 같은 수열을 만드는 것이 목적이기에,  첫번째 루프에서는 위 스택에서 4만 pop해서 출력을 하면 됩니다.

 

다음 루프에서는 "3" 이 오는데 이는 우리가 이전에 삽입 하였고, 이를 인덱스 값이 더 크다는 사실을 통해 알 수 있습니다.

 

그리하여, 별도의 push는 하지 않고 스택에 존재하는지 확인하여, 이를 Pop 해줍니다.

 

 

코드

let input = require("fs").readFileSync("/dev/stdin").toString().split("\n");
const n = Number(input[0]);
const stack = [];
let message = "";
let index = 1;

for (let i = 1; i <= n; i++) {
  let tmp = Number(input[i]);

  while (index <= tmp) {
    stack.push(index++);
    message += "+\n";
  }
  if (stack[stack.length - 1] === tmp) {
    message += "-\n";
    stack.pop();
  } else {
    message = "NO";
    break;
  }
}

console.log(message);