탑

문제

백준 2493번 - 탑

언어

JavaScript

순서도

스택에서 현재의 탑보다 작은 탑들을 모두 pop 합니다.
만약 스택이 빈 상태가 되면 현재의 탑보다 높은 탑은 없으므로 레이저 신호를 수신할 탑은 없으므로 0 으로 처리합니다.
만약 스택에 현재의 탑보다 큰 탑이 있다면 그 탑이 레이저 신호를 수신할 것이고 그 탑의 index 로 처리합니다.
현재의 탑을 스택에 넣습니다.

문제 풀이 step 1

이 문제는 스택을 이용해서 풀 수 있는 문제입니다. 그 이유는??
- 모든 탑이 레이저 신호를 왼쪽 방향으로 발사합니다.
- 그러므로 자신의 왼쪽부터 차례대로 탑의 정보를 얻을 수 있다면 상당히 효율적 풀 수 있을 것입니다.
- 이를 가능케 해줄 수 있는 자료구조가 스택입니다.
- 왜냐하면 스택에는 가장 최근에 넣은 탑이 맨 위에 있기 때문입니다. (LIFO)
주어진 모든 탑을 순회하면서 어떤 탑이 레이저 신호를 수신할 것인지 판단할 것입니다.
- 첫 번째 탑은 왼쪽에 어떤 탑도 없기 때문에 신호를 수신할 탑이 없습니다. 그래서 0 으로 처리 후 스택에 넣어줍니다.
- 두 번째 탑부터 자신의 왼쪽의 탑 정보들이 스택에 담겨있습니다.
  - 두 번째 탑 입장에서 스택 맨 위에 있는 탑이 자신보다 높다면 그 탑이 신호를 수신하게 될 것이니 그 탑의 index 로 처리후 스택에 넣어줍니다.
  - 만약 스택 맨 위에 있는 탑이 자신보다 낮다면 그 탑은 신호를 수신하지 못하니 0 으로 처리 후 스택에 넣어줍니다.
- 이후 과정은 두 번째 탑에서 했던 것과 같은 과정을 통해서 어떤 탑이 신호를 수신할 지 기록해주면 됩니다.
문제에서 원하는 것은 각 탑 기준으로 몇 번째 탑이 신호를 수신할 것인지이기 때문에 스택에는 탑의 index 를 넣어주면 더욱 쉽게 풀 수 있습니다.

후기

조건문의 순서를 어떻게 배치하느냐에 따라서 코드 라인 수와 직관성이 달라지는 것을 느낄 수 있었습니다.

맨 처음에 코드를 작성할 떄 스택이 비어있는지를 먼저 확인 후 이후 로직을 진행했는데 중복 코드가 발생했습니다.

for (let i = 0; i < n; i++) {
	if (stack.isEmpty()) {
		ans[i] = 0;
	} else {
		while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
			stack.pop();
		}

		if (stack.isEmpty()) {
			ans[i] = 0;
		} else {
			ans[i] = stack.peek() + 1;
		}
	}

	stack.push(i);
}

하지만 조건의 순서를 바꾸니 중복을 제거할 수 있었습니다.
매번 느끼지만 while 문이 반복문이지만 조건을 명시할 수 있기 때문에, 단순 반복문의 역할로만 쓰기 보다는 조건문의 역할도 할 수 있게 쓴다면 더욱 활용성을 높일 수 있는 것 같습니다.

소스 코드

const input = require("fs").readFileSync("/dev/stdin").toString().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() {
		if (!this.isEmpty()) return this.bucket[this.top];
	}
}

const solution = (input) => {
	const n = Number(input[0]);
	const arr = input[1].split(" ").map(Number);
	const ans = [];

	const stack = new Stack();
	for (let i = 0; i < n; i++) {
		//	스택에서 현재의 탑보다 작은 탑은 모두 pop 하기
		while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
			stack.pop();
		}

		// 스택에 탑이 없다면
		if (stack.isEmpty()) {
			ans[i] = 0;
		} else {
			ans[i] = stack.peek() + 1;
		}

		// 스택에 탑 넣어주기
		stack.push(i);
	}

	return ans.join(" ");
};

console.log(solution(input));