(프로그래머스 JS KAKAO)괄호 변환하기

https://programmers.co.kr/learn/courses/30/lessons/60058?language=javascript 

코딩테스트 연습 - 괄호 변환

 

스택과 재귀를 활용.

문제의 예시처럼 순서대로 코딩하면 된다.

 

isBalanced(string) 함수 설명:

인자로 받은 string 배열이 균형잡힌 괄호인지 확인하는 함수.

스택을 이용해 괄호를 검사한다.

stack이 비어있으면 string 배열은 균형잡힌 괄호라는 뜻으로 true를 반환한다.

 

reverse(string) 함수 설명:

인자로 받은 string 문자열을 첫번째 문자와 마지막 문자를 제외한 괄호를 뒤집어서 반환한다.

 

getString(p) 함수 설명:

p 문자열을 u, v로 나눠 각각을 검사한다.

p 문자열을 하나씩 파싱하여 left와 right의 개수를 세면서 stack 배열에 넣어준다.

left와 right가 같다면 stack이 균형잡힌 괄호인지 확인하자.

isBalanced() 함수를 통해 여부를 확인.

 

true라면

result에 stack 배열을 이어 붙인(stack.join("")) 문자열을 넣어주고, 나머지 문자열을 다시 재귀 함수를 통해 검사를 진행한다.(getString)

 

false라면

result에 "(" + getString(v) + ")" + reverse(u)를 한 결과를 넣어준다.

자동으로 재귀를 통해 답을 구할 수 있다.

function isBalanced(string){
    const stack = [];
    
    string.forEach((element) => {
        if(element === ')' && stack[stack.length - 1] === '('){
            stack.pop();
        }
        else{
            stack.push(element);
        }
    });
    
    return stack.length === 0 ? true : false;
}

function reverse(string){
    let result = "";
    
    for(let i = 1; i < string.length - 1; i++){
        if(string[i] === "("){
            result += ")";
        }
        else{
            result += "(";
        }
    }
    
    return result;
}

function getString(p){
    const result = [];
    const stack = [];
    let left = 0;
    let right = 0;
    let index = 0;
    
    while(index < p.length){
        if(p[index] === '('){
            left++;
        }
        else{
            right++;
        }
        stack.push(p[index++]);
        
        if(left === right){
            if(isBalanced(stack)){
                result.push(stack.join(""));
                result.push(getString(p.substr(index)));
                break;
            }
            else{
                result.push("(");
                result.push(getString(p.substr(index)));
                result.push(")");
                result.push(reverse(stack.join("")));
                break;
            }
        }
    }
    
    return result.join("");
}

function solution(p) {
    const answer = getString(p);
    
    return answer;
}