[백준] 2504번: 괄호의 값 (JavaScript, NodeJS)

문제

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.

1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 
2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. 
3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다. 

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다. 

입력

첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.

출력

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다. 

예제 입력 1 복사

(()[[]])([])

예제 출력 1 복사

28

예제 입력 2 복사

[][]((])

예제 출력 2 복사

0

정답 풀이

const path = process.platform === "linux" ? "/dev/stdin" : "input.txt"; // 리눅스로 테스트할 땐 따로 설정해주어야 합니다.
const input = require("fs").readFileSync(path).toString().trim().split("\n");

let [strings] = input;

// 문제 풀이
function solution(strings) {
	const string = strings.split('');
	const stack = [];

	if (!checkPossible(string)) {
		return 0;
	}

	for (let i = 0; i < string.length; i += 1) {
		let top = stack[stack.length - 1];
		const cur = string[i];

		if (cur === '(' || cur === '[') {
			stack.push(cur);
		} else if (cur === ')' || cur === ']') {
			const reverse = cur === ')' ? '(' : '[';
			const point = reverse === '(' ? 2 : 3;

			if (top === reverse) {
				stack.pop();
				stack.push(point);
			} else {
				let temp = 0;
				while (1) {
					const pop = stack.pop();
					if (typeof pop === 'number') {
						temp += pop;
					} else if (pop === reverse) {
						stack.push(temp * point);
						break;
					}
				}
			}
		}
	}
	return stack.reduce((acc, cur) => acc + cur);
}

function checkPossible(string) {
	const stack = [];
	for (let i = 0; i < string.length; i += 1) {
		let top = stack[stack.length - 1];
		const cur = string[i];

		if (cur === ']' && top === '[') {
			stack.pop();
		} else if (cur === ')' && top === '(') {
			stack.pop();
		} else {
			stack.push(cur);
		}
	}

	return stack.length ? false : true;
}

// 제출
const answer = solution(strings);
console.log(answer);

 

실버 문제 치고는 정말 어려운 문제였다..

올바른 괄호 문제는 쉽게 해결할 수 있는데

가운데 숫자가 껴있어서 조금 어려웠다.

 

핵심 아이디어는

1. '(' , '[' 를 만나면 스택에 넣는다.

2. 만약 ')' , ']' 를 만나면 그 때부터 문제다.

- 만약 스택의 top이 '(' 또는 '[' 를 만나면 숫자를 스택에 넣는다.

- 만약 스택의 top이 숫자면, '(' 또는 '[' 를 만날 때 까지 나오는 숫자들을 전부 더한다.

- '(' 또는 '[' 를 만나면 더한 숫자 * point(2 or 3)을 곱하고 스택에 넣는다.

4. 위의 과정을 string을 다 돌 때까지 진행한다.