스택 수열

문제

언어

  • JavaScript

문제 풀이 step 1

  • 스택을 이용합니다.
  • 스택의 맨 위의 값이 입력된 수열의 현재 위치 값보다 작다면 같아질 때까지 push를 진행합니다.
  • 스택의 맨 위의 값이 입력된 수열의 현재 위치 값과 같다면 pop을 진행합니다.
  • 만약 스택 맨 위의 값이 입력된 수열의 현재 위치 값과 다르다면 “NO”를 출력합니다.

후기

  • 스택 문제는 풀 때마다, 조건 분기가 간단하고 명료해야 문제없이 풀리는 느낌을 받습니다.
  • 이전에는 스택을 구현해서 풀 생각을 못해서, 다시 풀고 구현한 스택을 이용하는 소스 코드를 추가하였습니다.

소스 코드 1

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

const solution = (input) => {
	const N = parseInt(input[0]);
	const arr = input.slice(1, N + 1).map(Number);

	const stack = [];
	let step = 1;
	let res = "";
	for (let i = 0; i < N; i++) {
		while (stack.length <= 0 || stack[stack.length - 1] < arr[i]) {
			stack.push(step++);
			res += "+\n";
		}

		if (stack[stack.length - 1] === arr[i]) {
			stack.pop();
			res += "-\n";
		} else {
			return "NO";
		}
	}

	return res;
};

console.log(solution(input));

소스 코드 2

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

class Stack {
	constructor() {
		this.bucket = [];
		this.top = -1;
	}

	isEmpty() {
		return this.top === -1;
	}

	push(item) {
		this.bucket[++this.top] = item;
	}

	pop() {
		return this.bucket[this.top--];
	}

	peek() {
		return this.bucket[this.top];
	}
}

const solution = (input) => {
	const n = Number(input[0]);

	let index = 1;

	let res = "";
	const stack = new Stack();
	for (let i = 1; i < n + 1; i++) {
		const now = Number(input[i]);

		while (index <= now) {
			stack.push(index);
			res += "+\n";

			index += 1;
		}

		if (stack.peek() === now) {
			stack.pop();
			res += "-\n";
		} else {
			return "NO";
		}
	}

	return res;
};

console.log(solution(input));