s는 여러 괄호들로 이루어진 String 인자입니다. s가 유효한 표현인지 아닌지 true/false로 반환해주세요.
종류는'('
,')'
,'['
,']'
,'{'
,'}'
으로 총 6개 있습니다.
아래의 경우 유효합니다.
- 한 번 괄호를 시작했으면, 같은 괄호로 끝내야 한다.
- 괄호 순서가 맞아야 한다.
예를 들어 아래와 같습니다.
s = "()" // return true s = "()[]{}" // return true s = "(]" // return false s = "([)]" // return false s = "{[]}" // return true
function isValid(s) {
// 여기에 코드를 입력해주세요.
if (s.length % 2) {
return false;
}
const stack = [];
const bracketMatching = {
"(": ")",
"{": "}",
"[": "]",
};
for (let i = 0; i < s.length; i++) {
if (bracketMatching[s[i]]) {
stack.push(s[i]);
} else if (bracketMatching[stack.pop()] !== s[i]) {
return false;
}
}
return true;
}
문제를 보자마자 누구나 자료 구조와 알고리즘 책에서 본 문제임을 알았고, 스택 구조로 풀어야겠다고 생각했다. stack
이라는 빈 배열을 생성해두고, push
와 pop
메서드만을 사용해 문제를 풀어나갔다.
처음에는 if (s.length % 2) return false;
라는 조건을 달지 않았는데, 테스트 케이스 중 "("
인 것이 있었고, 만일 글자 수가 홀수라면 당연히 짝이 맞지 않는 것이니 로직의 진행에 앞서 가장 먼저 심사 후 처리해주었다.
여는 괄호라면 stack
배열에 추가하고, 닫는 괄호라면 stack
을 팝해 bracketMatching
객체에 넣어 짝이 맞는지 검사한다. 만일 맞는 짝이라면 추가 동작을 하진 않지만, stack
에선 이미 마지막으로 들어간 여는 괄호가 pop
되어 나간 상태라는 점을 이용했다.