728x90
반응형
올바른 괄호
❓ 문제설명
괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다.
예를 들어
"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.
🚫 제한조건
문자열 s의 길이 : 100,000 이하의 자연수
문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.
✔ 입출력 예
| s | answer |
| "()()" | true |
| "(())()" | true |
| ")()(" | false |
| "(()(" | false |
💡 풀이
function solution(s){
// 내 풀이
// 큐를 사용해서 문자열을 순차적으로 순회하고
// 스택을 사용하여 문자를 저장하며 괄호의 완성을 체크한다.
const stack = []
let queue = s
// '(', ')' 문자의 수가 다르다면 false
if (s.replace(/\)/g,'').length !== s.replace(/\(/g,'').length) {
return false
}
while (queue.length > 0) {
const c = queue.charAt(0)
queue = queue.substring(1)
if (stack.length === 0 && c === ')') {
// 스택이 ')'로 시작하면 false
return false
}
if (c === ')' && stack[stack.length - 1] === '(') {
// 괄호가 완성되면 스택에서 괄호 쌍을 비운다.
stack.pop()
} else {
stack.push(c)
}
}
return stack.length > 0 ? false : true
// 다른사람 풀이
// 괄호를 각 1, -1로 매칭해서 문자열을 돌면서 그 합을 확인한다. (0이라면 true)
let cum = 0
// '(', ')' 문자의 수가 다르다면 false
if (s.replace(/\)/g,'').length !== s.replace(/\(/g,'').length) {
return false
}
for (let paren of s) {
cum += paren === '('? 1: -1
if(cum < 0) {
// ')'로 시작한다면 false
return false
}
}
return cum === 0? true: false;
}📝 해설
스택과 큐를 사용해서 문자열 s를 큐 대기열로 순회하여 스택에 쌓고, 스택에서는 괄호가 완성 되었을 경우 괄호 쌍을 삭제하여 최종적인 스택의 길이가 0이라면 true / 그 외에는 false를 리턴하였다. 이 때 시간초과가 발생하기 때문에 최초에 '(' 과 ')' 갯수가 동일하게 들어오는지 그리고 스택이 비어있을 때 처음 들어오는 값 이 ')' 인지 확인해서 미리 false를 리턴하는 로직을 넣어서 시간초과를 해결하였다.
다른사람의 풀이를 보다보니 괄호를 각각 1 과 -1에 매칭하여 단순히 더하는 것으로 해결한 방법이 있었다. 속도나 메모리는 차이가 없었지만 생각을 전환해볼 수 있는 방법이라 따로 추가하였다.
📚 참고자료
- https://kimby.tistory.com/84 (String 메소드)
728x90
반응형
