: 올바른 괄호란 (
로 열려서 )
로 닫혀야 한다는 뜻
(
또는 )
로만 이루어져 있다.()()
→ true
(())()
→ true
)()(
→ false
(()(
→ false
이 문제는 스택(Stack) 문제이다.
만약 입력값이 (())()
라고 할 때, Stack에 요소를 하나씩 push한다.
그러다가 Stack에 ()
가 생기면, pop해준다.
push [(]
→ push [(,(]
→ push [ (,(,) ]
→ pop [(]
→ push [(,)]
→ pop []
→ push [(]
→ push [(,)]
→ pop []
// 빈 배열(Stack)을 만든다.
// 문자열을 반복문으로 돌릴 건데,
// 만약 문자(char)가 여는 괄호'('라면, 스택에 push한다.
// 만약 문자가 닫는 괄호 ')'라면,
// 빈 배열에 ')'가 들어가는 경우는 바로 false를 리턴한다.
// 빈 배열이 아니라면 여는 괄호가 있을테니, 스택을 pop해준다.
// 반복문이 끝나고, 스택에 요소가 남아있지 않으면 true, 남아있다면 false를 리턴한다.
function solution(string) {
const stack = [];
for (const char of string) {
if (char === '(') { // 여는 괄호일 경우
stack.push(char);
} else { // 닫는 괄호일 경우
if (stack.length === 0) { // 스택이 비어있다면
return false; // false를 리턴한다.
} // 스택이 비어있지 않다면
stack.pop(); // stack의 마지막 요소를 없앤다.
}
}
// 반복문이 종료된 후,
return stack.length === 0; // 스택의 길이가 0이면 true, 0이 아니라면 false를 리턴한다.
}
스택의 방식을 이용하지만, 스택을 사용하지 않은 풀이
function solution(string) {
let count = 0; // count 변수 선언
for (const char of string) {
if (char === '(') { // 여는 괄호일 경우
count += 1; // count에 1 증가시킨다.
} else { // 닫는 괄호일 경우
if (count === 0) { // count가 0이면
return false; // false를 리턴한다.
} // count가 0이 아니라면
count -= 1; // count에서 1을 뺀다.
}
}
return count === 0; // count가 0이면 true, 0이 아니라면 false를 리턴한다.
}