[백준 | 1874 | 자바스크립트] 스택 수열

문제

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

 

정답 코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";

const input = fs
  .readFileSync(filePath)
  .toString()
  .split("\n")
  .map((i) => Number(i));

function solution(input) {
  const result = [];
  const count = input[0];
  const stack = [];
  let stackNumber = 1;

  for (let i = 1; i <= count; i++) {
    while (stackNumber <= input[i]) {
      stack.push(stackNumber);
      result.push("+");
      stackNumber++;
    }

    if (stack[stack.length - 1] === input[i]) {
      result.push("-");
      stack.pop();
    } else {
      return ["NO"];
    }
  }

  return result;
}

console.log(solution(input).join("\n"));

 

풀이

문제를 읽고 어떻게 풀라는 것인지 이해가 안갔다. 그래서 이것저것 찾아보며 문제 이해부터 했다.

 

문제 이해하기

예시

4
1
2
4
3

// 출력 
+
-
+
-
+
+
-
-

아래 흐름으로 문제 먼저 이해해보았다.

 

초기 상태

• 스택: [] (비어 있음)
• 현재 push 가능한 숫자: 1부터 시작

1. 첫 번째 숫자: 1

• 현재 스택: []
• 수열의 첫 번째 숫자 1을 만들기 위해 push.

• push 1 → 스택: [1] → 연산: +

• 스택의 맨 위 숫자 1이 수열의 첫 번째 숫자 1과 같으므로 pop.

• pop → 스택: [] → 연산: -

2. 두 번째 숫자: 2

• 현재 스택: []
• 수열의 두 번째 숫자 2를 만들기 위해 push.

• push 2 → 스택: [2] → 연산: +

• 스택의 맨 위 숫자 2가 수열의 두 번째 숫자 2와 같으므로 pop.

• pop → 스택: [] → 연산: -

3. 세 번째 숫자: 4

• 현재 스택: []
• 수열의 세 번째 숫자 4를 만들기 위해 push 연산으로 3, 4를 넣어야 한다.

• push 3 → 스택: [3] → 연산: +
• push 4 → 스택: [3, 4] → 연산: +

• 스택의 맨 위 숫자 4가 수열의 세 번째 숫자 4와 같으므로 pop.

• pop → 스택: [3] → 연산: -

4. 네 번째 숫자: 3

• 현재 스택: [3]
• 스택의 맨 위 숫자 3이 수열의 네 번째 숫자 3과 같으므로 pop.

• pop → 스택: [] → 연산: -

 

문제 풀이

• result : 스택 연산 기록을 저장
• stack : 스택 데이터 구조
• stackNumber : 스택에 넣을 숫자 추적 (1부터 시작)

 

while (stackNumber <= input[i]) {
  stack.push(stackNumber);  // 스택에 숫자 추가
  result.push("+");  // 연산 기록
  stackNumber++;  // 다음 숫자로 이동
}

• 현재 수열의 값(input[i])을 만들기 위해, 스택에 숫자를 오름차순으로 추가(push)
• stackNumber를 하나씩 증가시키며 스택에 값 쌓기
• 각 push 연산은 "+"로 기록

 

if (stack[stack.length - 1] === input[i]) {
  result.push("-");  // 연산 기록
  stack.pop();  // 스택에서 숫자 제거
} else {
  return ["NO"];  // 수열을 만들 수 없는 경우
}

• 스택의 맨 위 값(stack[stack.length - 1])이 수열의 값(input[i])과 같다면, 스택에서 값을 제거(pop)
• pop 연산은 "-"로 기록
• 만약 스택의 맨 위 값이 수열의 값과 다르다면, 주어진 수열을 만들 수 없으므로 즉시 "NO"를 반환