프로그래머스 [올바른 괄호]

자료구조 Stack

• 자료구조 stack을 이용하여 해결 가능한 문제이다.

풀이 과정

• 빈 스택을 선언한다.
• 문제에서 주어지는 문자열을 순차적으로 탐색하며, 요소가 여는 괄호일 경우 해당 요소를 스택에 push, 닫는 괄호일 경우 빈 스택이 아닐 경우에는 이미 존재하는 스택의 맨 상단 요소를 pop한다.
  • 빈 스택일 경우에 탐색된 요소가 닫는 괄호일 경우 괄호들의 짝이 맞을 수가 없기 때문이다.
• 문자열을 모두 순회하고 난 뒤, 스택의 길이가 0이면 true, 아니면 false를 반환한다.

내가 작성한 풀이 코드

function solution(s){
    if(s[0] === ')') {
        return false
    }
    let stack = []
    for(let i = 0; i < s.length; i++) {
        // stack에 들어가게될 s의 i번째 요소가 '' 일 경우 그 앞에 요소가 '' 일 경우 제거
        if(s[i] === ')') {
            if(stack[stack.length - 1] === '(') {
                stack.pop()
            }
        }
        else stack.push(s[i])
    }
    return Boolean(stack.length === 0)
}

개선할 사항

사실 위 코드에서 순회되는 요소가 닫는 괄호일 경우엔, 스택에서 최상단 요소가 여는 괄호인지 확인할 필요가 없다.(stack에 push되는 경우는 여는 괄호인 경우 밖에 없기 때문이다.)
즉 정리하자면, 닫는 괄호가 발견되면 이미 stack에 들어가있는 여는 괄호를 제거하게 되는 것이다. 이는 둘이 짝지어 제거되는 것과 같다. 그리고 빈 스택일 경우 닫는 괄호가 발견되면 반드시 false를 return하도록 예외처리를 해주어야 한다.

그리고 사실 위 코드를 보면, stack에 push와 pop만 하고 stack의 길이만 이용하고 있고 내부 요소를 이용하지 않고 있다. 따라서 배열을 선언해도 좋지만 count 변수에 0을 선언하여 count의 값이 0이 아니며 닫는 괄호인 경우 count에 -1을, 그리고 여는 괄호인 경우, 즉 stack에 push하는 경우엔 +1을 해주는 방식으로도 풀이가 가능하다. 이 방법이 메모리 효율성이 더 높다.

function solution(s){
    if(s[0] === ')') {
        return false
    }
    let count = 0
    for(let i = 0; i < s.length; i++) {
        // stack에 들어가게될 s의 i번째 요소가 '' 일 경우 그 앞에 요소가 '' 일 경우 제거
        if(s[i] === ')') {
            if(count === 0) return false
                else {
                    count -= 1 
                }
       
        }
        else count += 1
    }
    return count === 0
}