[프로그래머스/JS] Level2 - 올바른 괄호 # 고차함수 # 스택

 

https://school.programmers.co.kr/learn/courses/30/lessons/12909

프로그래머스

 

올바른 괄호 문제이다! 스택을 활용해 풀 수 있다!

문자열에 reduce는 안됨. 그러나 for of 루프 돌며 원소 하나씩 탐색 가능함
문자열도 마찬가지로 Array.from()이나 [... string]으로 Array로 변환해야 Array.고차함수 쓸 수 있음

 

접근 방법

 

 

이 문제의 첫 접근은 아래와 같이 풀었습니다. ')' 가 보이면 스택에 넣고, 현재 탐색중인 원소가 ')' 면 top과 짝을 이루면 방출 아닐 경우 스택에 추가. 그렇게 한번 문자열을 탐색하면, 결과적으로 스택은 비어있어야 올바른 괄호가 됩니다.

 

풀이 1

function solution(s){
    return Array.from(s).reduce(
        (stack, value) => {
            if (stack.length === 0) {
                stack.push(value)
                return stack
            }
            let last = stack.at(-1)
            if (last == '(' && value == ')') {
                stack.pop()
            } else {
                stack.push(value)
            }

            return stack
        }, []).length == 0 
}

 

 

풀이 2

 

'(' 와 ')' 단 두 가지 종류는 1, -1로 바꿀수도 있습니다. 

 

그렇다면 문자열을 탐색하면서  '(' 일때는 +1을 , ')'일 때는 -1을 누적으로 더하면 그래도 올바른 괄호가 나옵니다.

그러나 ')'와 '(' 가 나와도 0이기 때문에 조건을 달아야 합니다.  ')'가 먼저 나오는 순간 누적 값이 -1이 되고, -1이 된 경우는 무조건 올바른 괄호일 수 없습니다.

 

function solution(s){
    return [...s].reduce(
        (acc, value) => { 
            acc += value === '(' ? 1 : -1
            if (acc === -1) return -100000
            return acc
        }, 0) === 0
}