쇠막대기(Stack)

:raising_hand: 알고리즘 공부 간 기록이 필요한 문제들에 대한 정리를 기록하는 포스트 입니다.

1. 문제 요건

괄호의 조합(ex. ()(())()()) 을 입력받으며, ’(‘ 문자는 쇠막대기가 추가된다고 가정하고 ’()’ 의 경우 해당 시점의 막대기를 자른다고 생각한다. 입력받은 조합에서 몇개의 막대기가 나오는지 구한다.

2. 코드

function solution(a) {
    let stack = []
    let answer = 0
    for(let i=0; i<a.length; i++) {
        if(a[i]==='(') {
            stack.push(a[i])
        } else {
            stack.pop()
            if(a[i-1] === ')') {
                answer += 1
            } else {
                answer += stack.length
            }
        }
    }
    return answer
}
function mySolution(a) {
    let stack = []
    let beforeFlag = 'N'
    let raiser = band = 0
    for(let x of a) {
        if(x === '(') {
            if((stack.length !== 0) && beforeFlag === 'N') {
                band -= raiser
            }
            beforeFlag = 'N'
            stack.push(x)
        } else {
            if(beforeFlag === 'Y') {
                stack.pop()
                band += (raiser+1)
            } else {
                beforeFlag = 'Y'
                stack.pop()
                raiser++
            }
        }
    }
    return band
}
let value = '()(((()())(())()))(())'
console.log(solution(value))

3. 결과정리

먼저 이문제의 핵심은 막대기가 끝날때 어떤 로직으로 막대기의 갯수를 추가하는지 이다.

내가 첫번째 풀어본 아이디어는 막대기가 끊어질때(‘))’) 의 경우 해당시점에 생기는 막대의 갯수(레이저 + 1)만큼을 더하는 것을 기본 전제로 가정한다. 그러나 해당시점에 끊기지 않은 막대기도 있으나, 다시 막대기가 그 사이에 추가된경우 추가된 막대기가 끝날경우 추가적인 막대기갯수가 더해질 것이므로 그럴 경우를 대비해 중간에 추가되는 경우에는 미리 추가될 막대기 갯수(레이저 갯수) 만큼을 뺴주게 된다.

하지만, 해당 문제는 더 간단하게 푸는 방법은 오로지 레이저가 닫히는 경우 추가되는 막대 갯수를 빼주는 것이다.

레이저가 닫힐때마다 그때까지의 막대의 갯수(stack안의 ‘(‘) 의 갯수 를 더해주고 막대가 끝나는 경우마다 추가로 +1 을 해주면 된다.

You may also enjoy