Programmers - 괄호 변환 (Javascript)

function correctStr(str){    
    let cnt = 0;
    for(let i=0; i<str.length ; i++){
        if(str[i]==='(') cnt+=1;
        if(str[i]===')') cnt-=1;
        if(cnt<0) return false;//올바르지 않은 문자열
    }
    return cnt===0;//균형잡힌 문자열
}


function getUV(str){//2.문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리
    let left, right , u, v, tempU, tempV;
    
    left=right=0;
    u = v = "";
    
    for(let i=0; i< str.length ; i++){
        if(str[i]==="(") left++;
        if(str[i]===")") right++;
        
        if(left===right){
            u = str.slice(0,i+1);
            v = str.slice(i+1);
            break;
        }
    }
  
    return {u,v};
}


function changeU(u){//4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙임.
    let str = u.slice(1,u.length-1);
    let arr = str.split('').map((c)=>{
        if(c==="(")return ")";
        if(c===")")return "(";
    })
    return arr.join('');
}

function recursive(str){
    if(str === "") return str;//1.입력이 빈 문자열인 경우, 빈 문자열을 반환
    
    let {u,v} = getUV(str);//2.문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리
    
    if(correctStr(u)){//3.문자열 u가 "올바른 괄호 문자열" 
        return u+recursive(v);//3.문자열 v에 대해 1단계부터 다시 수행 + 3-1.수행한 결과 문자열을 u에 이어 붙인 후 반환
    }else{
        return "("+recursive(v)+")"+changeU(u);//4-1~4-5
    } 
}

function solution(p) {
    let answer = '';
    if(correctStr(p)) return p;//이미 올바른 괄호 문자열
    answer = recursive(p);
    return answer;
}

주어진대로 구현만하면 되는 문제였다. 포인트는 두 부분이었다.

u와 v 분리

u와 v는 여는괄호와 닫는괄호의 개수가 처음으로 같아지는 시점에 분리했다. 이렇게 하게되면 u는 균형잡힌 괄호 문자열로 더 이상 분리할 수 없다는 조건과 균형잡힌 괄호 문자열 u, v로 분리한다는 조건 모두 만족하게 된다. 후자가 만족되는 이유는 입력이 균형잡힌 문자열로 들어오기 때문에 u가 균형잡힌 문자열이라면, v도 균형잡힌 문자열이 되기 때문이다.

균형잡힌 문자열, 올바른 문자열

correctStr 함수는 균형잡힌 문자열, 올바른 문자열 모두를 검사할 수 있도록 만들었다. 여는괄호에 +1 , 닫는괄호에 -1을 부여하고 누적시키다가 음수가 나오면 닫는괄호가 더 많이 나왔다는 말이고, 이는 올바르지 않은 문자열이 된다. 또한 이 경우 결과 누적값이 0이여야만 균형잡힌 문자열이다.