좋은 단어

문제

언어

  • JavaScript

문제 풀이 step 1

  • 본 문제는 스택 유형의 올바른 괄호 찾기 문제와 유사합니다.
  • 다른점은 올바른 괄호 찾기 문제에서는 여는 괄호와 닫는 괄호가 구분이 되지만, 본 문제는 같은 글자인지만 구분하면 됩니다.

문제 풀이 step 2

  • 문제에서 단어 위로 아치형 곡선을 그어 같은 글자끼리 (A는 A끼리, B는 B끼리) 쌍을 짓고, 선끼리 교차하는지를 판별한다고 했습니다.
  • 위 방법은 사람의 입장에서 가능한 방법입니다. 컴퓨터 입장에서는 스택을 이용해서 위 방법을 구현할 수 있습니다.
  • 선이 교차하게 되는 경우는 여는 글자와 닫는 글자 사이엔 닫히지 않은 여는 글자가 있는 경우입니다.
    • 예를 들면,
    • A(여는 글자) B(여는 글자) A(닫는 글자)
    • 위의 형식처럼 A(여는 글자) 와 A(닫는 글자) 사이에 닫히지 않은 B(여는 글자) 가 있는 경우를 말합니다.
  • 선이 교차하지 않는 경우는 여는 글자와 닫는 글자 사이에 글자가 없거나, 여는 글자와 닫는 글자 쌍이 존재하는 경우입니다.
    • 예를 들면,
    • A(여는 글자) B(여는 글자) B(닫는 글자) A(닫는 글자)
    • 위의 형식처럼 B 사이에는 글자가 없고, A 사이에는 글자가 있지만 여는 글자와 닫는 글자 쌍이 존재하는 경우입니다.

문제 풀이 step 3

  • 스택을 이용해서 주어진 단어를 한 글자씩 넣다가 스택의 맨 위에 있는 글자와 비교해서 여는 글자와 닫는 글자의 쌍이 맞다면 pop 을 해주고, 아니라면 일단 push 를 해주는 방식을 통해서 이 문제를 풀 수 있습니다.
  • 만약 주어진 단어가 좋은 단어라면 그 안의 글자들은 모두 여는 글자와 닫는 글자의 쌍이 정확히 맞아떨어질 것입니다.
    • 따라서 그 경우에는 스택에 넣고 뺐을 때 스택이 텅 비게 됩니다.
  • 반면 주어진 단어가 좋은 단어가 아니라면 스택에 넣고 뺏을 때, 스택에 글자들이 남아있겠죠??
  • 이 두 경우에 따라서 주어진 단어가 좋은 단어인지 판별하면 됩니다.

문제 풀이 step 4

  • 제가 이해를 돕기 위해서 여는 문자와 닫는 문자라고 명시를 했지만, 사실 주어진 단어에서 각 글자가 여는 글자인지 닫는 글자인지는 판별은 안됩니다.
  • 하지만 스택을 이용해서 주어진 단어를 한 사이클 돌려서 스택이 텅 비게 되면, 주어진 단어의 각 글자가 여는 글자인지 닫는 글자인지 상관없이 각 글자의 쌍이 맞아떨어진다는 것이고, 좋은 단어라고 판별할 수 있는 것입니다.

소스 코드

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 checkGoodWord = (charArr) => {
	const stack = new Stack();

	for (let i = 0; i < charArr.length; i++) {
		if (!stack.isEmpty() && stack.peek() === charArr[i]) {
			// 글자의 쌍이 맞아 떨어진다면 pop
			stack.pop();
			continue;
		}

		// 쌍이 맞아 떨어지지 않는다면 push
		stack.push(charArr[i]);
	}

	return stack.isEmpty();
};

const solution = (input) => {
	const n = Number(input[0]);
	let ans = 0;
	for (let i = 1; i < n + 1; i++) {
		const charArr = input[i].split("");

		if (checkGoodWord(charArr)) ans++;
	}

	return ans;
};

console.log(solution(input));