막대기

문제

언어

  • JavaScript

순서도

  1. 간단한 스택 구현 또는 배열 사용
  2. 스택에 막대기 넣기, 이 때 현재의 막대기보다 작은 이전의 막대기들은 제거
  3. 스택에 남아있는 막대기의 개수 출력

문제 풀이 step 1

  • 왼쪽부터 순차적으로 막대기를 일렬로 세우고, 오른쪽에서 보이는 막대기의 개수를 세는 문제입니다.
  • 일렬로 세운 막대기를 오른쪽에서 볼 때, 큰 막대기 하나를 기준으로 그 뒤에 작은 막대기들은 보이지 않습니다.
  • 그래서 막대기를 하나씩 스택에 넣으면서, 현재 넣으려는 막대기보다 작은 막대기들은 스택에서 제거합니다.
  • 스택을 이용하고 있으니, 작은 막대기를 제거하는 과정에서 가장 최근의 막대기부터 하나씩 제거할 수 있습니다.
  • 제거를 진행하다가 현재 넣으려는 막대기보다 큰 막대기를 만나면 더 이상 제거하지 않고, 현재 넣으려는 막대기를 넣어줍니다.
  • 이 문제는 스택의 가장 최근에 넣은 데이터가 가장 먼저 나오는 후입선출 특성을 이용해서 순조롭게 풀 수 있는 문제입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

소스 코드

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(data) {
		this.bucket[++this.top] = data;
	}

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

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

	size() {
		return this.top + 1;
	}
}

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

	const stack = new Stack();

	for (let i = 1; i < n + 1; i++) {
		// 현재 넣으려는 막대기
		const barHeight = Number(input[i]);

		// 스택이 비어있지 않고, 가장 최근의 막대기가 현재 넣으려는 막대기보다 작다면
		while (!stack.isEmpty() && stack.peek() <= barHeight) {
			// 제거
			stack.pop();
		}

		// 현재 넣으려는 막대기 넣기
		stack.push(barHeight);
	}

	// 스택에 남아있는 막대기의 개수 출력
	return stack.size();
};

console.log(solution(input));