baekjoon. 괄호의 값

문제

링크

2504번: 괄호의 값

풀이

보통 올바른 괄호를 찾는 문제에서 응용해서 풀어야하는 문제

(()[[]])([])를 예로 들어보자

앞부분 부터 스택에 하나씩 넣으면서 올바른 한 쌍이되면 한 쌍을 빼고 숫자를 삽입해야한다

(

()[[]])([])

(

(

)[[]])([])

그러다 올바른 괄호 한 쌍이 만나면 괄호가 pop되는 것까진 동일한데 여기서 2를 삽입한다

2

(

[[]])([])

[

2

(

[]])([])

[

[

2

(

]])([])

이제 [와 ]가 만나면 괄호를 빼주고 대신 3을 삽입한다

3

[

2

(

])([])

]

3

[

2

(

)([])

여기서 닫는 괄호가 나와서 스택의 마지막 값과 비교해 올바른 괄호인지 확인해야하는데 숫자라서 불가능하다

이 때 스택을 계속 pop해 주면서 현재 괄호값과 한 쌍이되는 값을 찾아주면 되는데 그 과정에서 pop되는 정수들은 모두 합해주고 쌍이 맞는 괄호를 찾았다면 정수의 합과 곱()는 2 []는 3해주면된다

9

2

(

코드

    const readline = require('readline');

    const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout
    });
    let input = ''
    rl.on('line', function(line) {
        input += line+'\n';
        rl.close();
    }).on('close',function (){
        solution(input.slice(0,-1))
        process.exit();
    });

    function solution(input){
        const ps = input.split('')
        console.log(sumPs(ps))
    }

    function findOpener(target,stack) {
        let sum = 0

        while (stack.length){
            const temp = stack.pop()
            if(!isNaN(Number(temp))){
                sum += temp
                continue
            }
            if(temp===target) return target === '(' ? sum*2 : sum*3
            return false
        }

    }

    function sumPs(ps){
        const stack = []

        while (ps.length) {
            const temp = ps.shift()
            if(!(temp === '['||temp === '('||temp === ']'||temp === ')')) return 0
            if (!stack.length) {
                if (temp === ')' || temp === ']') return 0
                stack.push(temp)
                continue
            }

            if(temp==='['){
                stack.push(temp)
                continue
            }
            if(temp==='('){
                stack.push(temp)
                continue
            }

            if(temp===']'){
                if(stack[stack.length-1]==='('){
                    return 0
                }
                if(stack[stack.length-1]==='['){
                    stack.pop()
                    stack.push(3)
                    continue
                }
                const result = findOpener('[',stack)
                if(!result) return 0
                stack.push(result)
            }

            if(temp===')'){
                if(stack[stack.length-1]==='['){
                    return 0
                }
                if(stack[stack.length-1]==='('){
                    stack.pop()
                    stack.push(2)
                    continue
                }
                const result = findOpener('(',stack)
                if(!result) return 0
                stack.push(result)
            }
        }
        const answer = stack.reduce((acc,v)=>acc+v,0)

        return isNaN(Number(answer))? 0 : answer
    }