[Algorithm] Balance Brackets in JS ( 스택(stack) 알고리즘 활용 )

 

스택(Stack) 자료구조를 활용한 Bracket Balance 알고리즘 문제입니다. 알고리즘 문제를 해결할 때 어떤 부분이 가장 중요하다고 생각하나요? 문제를 접하고 어떤 알고리즘이 가장 적합한지 생각한 후 풀이를 확인하시면 실력이 쑥쑥 늘어납니다!

 

 

문제

 

임의의 문자열을 입력받아 문자열 내 모든 괄호의 Pair가 맞는지 확인한 후 결과를 반환합니다.

 

입력 

string 타입의 괄호로 구성된 문자열

 

출력

Boolean 타입

 

주의사항

괄호는 먼저 열리고 ( '(' ) 닫혀야 ( ')' ) 합니다. 빈 문자열을 입력받는 경우 true를 반환해야 합니다. 괄호는 열린 만큼만 닫혀야 합니다. 

 

예시

let output = balancedBrackets('(');
console.log(output); // // -> false

output = balancedBrackets('()');
console.log(output); // --> true

 

문제 풀이

 

알고리즘 문제를 풀 때 가장 중요한게 무엇일까요? 많은 답변이 있겠지만 개인적으로 어떤 자료구조가 활용될 수 있을까? 고민해보는게 첫번째 풀이 단계라고 생각합니다. 이번 문제는 괄호(Brackets)의 짝을 찾는 문제입니다. 모든 경우의 수를 생각해서 Brute Force로 과연 문제를 해결할 수 있을까요?

 

중간에 나오는 Brackets들의 경우의 수를 생각해서 조건문을 분기시키다 보면 굉장히 복잡하고 Fragible한 로직이 완성됩니다. 어떤 생각지 못한 예외의 경우만 나와도 오류를 발생시키기 쉬운 로직입니다. 문제를 처음 접하고 단순한 생각으로 조건문을 분기하다 보니 아래와 같은 프랑켄슈타인 알고리즘이 탄생했습니다.

 

const balancedBrackets = function (str) {
    // TODO: 여기에 코드를 작성합니다.


    const strArr = str.split('');


    // 1. 전체 브라켓 검사 진행
    const a_count1 = strArr.filter(item=>item==='(').length;
    const a_count2 = strArr.filter(item=>item===')').length;
    
    const b_count1 = strArr.filter(item=>item==='[').length;
    const b_count2 = strArr.filter(item=>item===']').length;

    const c_count1 = strArr.filter(item=>item==='{').length;
    const c_count2 = strArr.filter(item=>item==='}').length;

    if(a_count1 !== a_count2) return false;
    else if(b_count1 !== b_count2) return false;
    else if(c_count1 !== c_count2) return false;


    // 2. 개별 브라켓 검사

    // 2-1 첫번째 브라켓
    if(strArr[0]===')' || strArr[0]===']' || strArr[0]==='}') 
        return false;
    

    // // 2-2 두번째 브라켓 부터 검사 진행
    for(let i=1; i<strArr.length; i++){
        if(strArr[i] === ')'){
            const temp1 = strArr.slice(0, i+1).filter(item=>item==='(').length;
            const temp2 = strArr.slice(0, i+1).filter(item=>item===')').length;
            console.log(temp1, temp2);
            if(temp1!==temp2) return false;
            if(strArr[i-1] !== '(') return false;
        }
        else if(strArr[i] === '}') {
            const temp1 = strArr.slice(0, i+1).filter(item=>item==='{').length;
            const temp2 = strArr.slice(0, i+1).filter(item=>item==='}').length;
            console.log(temp1, temp2);
            if(temp1!==temp2) return false;
            if(strArr[i-1] !== '}') return false;
            
        }else if(strArr[i] === ']') {
            const temp1 = strArr.slice(0, i+1).filter(item=>item==='[').length;
            const temp2 = strArr.slice(0, i+1).filter(item=>item===']').length;
            console.log(temp1, temp2);
            if(temp1!==temp2) return false;
            if(strArr[i-1] !== ']') return false;
        }
    }

    return true;
  };

 

이번 문제의 핵심은 STACK 자료구조를 사용하는 것입니다. STACK은 가장 대표적인 LIFO(Last In, First Out) 방식의 자료구조로써 우선적으로 나열된 브라켓의 짝을 찾기에 안성맞춤인 자료구조입니다. 

 

예를 들어 아래와 같은 입력이 있다고 가정합니다. 차례로 Bracket이 열리고(Opener) 열린 수 만큼 닫혀야(Closer) 합니다. Bracket이 짝을 찾는 순서는 가장 뒤에 추가된 Bracket 부터 자신의 짝을 찾게 됩니다. 

 

for문을 순회하면서 만약 close가 등장한 경우 Stack에 추가되어 있는 Opener를 확인합니다. 가장 먼저 '[' Bracket이 Stack에서 출력됩니다. 

 

Stack Pointer는 1만큼 감소하게 되고, 반복중인 현재 문자열이 Stack에서 출력된 문자열에 상응하는 closer인지만 확인하면 됩니다.

 

만약 주어진 Bracket으로 구성된 문자열을 모두 순회한 이후 Stack이 0이 아니라면 자신의 짝을 찾지 못한 녀석이 존재한다는 말이 됩니다. 또한 Stack에서 출력된 문자열에 상응하는 Closer를 찾지 못한 경우도 자신의 짝을 찾지 못한 경우가 될 수 있습니다.

 

Stack을 활용한 위와 같은 로직을 Javascript로 구현하면 아래와 같습니다.

 

const balancedBrackets = function (str) {

    const opener = {
        '(' : ')',
        '{' : '}',
        '[' : ']',

    };
    const closer = ')}]';
    const stack = [];

    for(let i=0; i<str.length; i++){
        if(Object.keys(opener).includes(str[i])){
            stack.push(str[i]);
        }
        else if(closer.includes(str[i])){
            const temp = stack.pop();
            if(opener[temp] !== str[i]){
                return false;
            }
        }
    }

    return stack.length === 0;
}

 

 

 

 

[Algorithm] BFS Queue 자바스크립트(primePassword 문제) 구현

 

[Backtracking] 백준 15651 N과 M 3단계 Node.js 구현하기

 

[Algorithm] treeBFS 알고리즘 Javascript Node.js 구현하기