프로그래머스 괄호 변환 JavaScript

2023년 5월 15일

프로그래머스 괄호 변환

문제 풀이

'(' 와 ')'로만 이루어진 문자열이 있을 때, '('의 개수와 ')'의 개수가 같다면 이를 균형잡힌 괄호 문자열이라 하고 '('와 ')'의 짝도 모두 맞을 경우 올바른 괄호 문자열 이라 한다. 균형잡힌 괄호 문자열인 경우 올바른 괄호 문자열로 변환해서 반환하는 문제다.

처음에 문제 이해가 되지 않아 문제에서 주어진 과정대로 해결했다.

index.md

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
  3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
  4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
  4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
  4-3. ')'를 다시 붙입니다. 
  4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
  4-5. 생성된 문자열을 반환합니다.

function checkCorrectStr(str): 문자열 str을 매개변수로 받아 올바른 괄호 문자열인지 확인하는 함수, 올바른 괄호 문자열인 경우 true를 아니면 false를 반환한다.
자료구조 스택을 이용해 str을 순회하면서 현재 인덱스의 문자가 '(' 인 경우 push,
')'인 경우일 때 stack에 요소가 있으면 pop 하고, 비어있으면 올바르지 못한 문자열이므로 false를 반환한다. (예: '())(' )
function findDivideIndex(str): 문자열 str을 매개변수로 받아 균형잡힌 괄호 문자열로 더 이상 분리할 수 없는 문자열로 분리하는 인덱스를 찾아 반환한다.
'('의 개수를 left로 ')'의 개수를 right 변수로 카운트하여 left와 right가 0이 아니면서 같을 때 더 이상 분리할 수 없는 균형잡힌 괄호 문자열이 된다.

solution.js

function solution(p) {
    let answer = '';
    
    if (checkCorrectStr(p)) {
        return p;
    }
    
    const recursive = (w) => {
        // 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
        if (w === '') {
            return '';
        }

        // 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 
        const idx = findDivideIndex(w);
        let u = w.slice(0, idx + 1);
        let v = w.slice(idx + 1);
        
        // 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
        if (checkCorrectStr(u)) {
            // 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 
            return u + recursive(v);
        }
        // 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
        else {
            // 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
            let newStr = '('; 
            //  4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
            newStr += recursive(v);
            // 4-3. ')'를 다시 붙입니다. 
            newStr += ')';
    
            // 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
            u = u.slice(1, u.length - 1);
            let u_reverse = '';

            for (let i = 0; i < u.length; i++) {
                u_reverse += u[i] === ')' ? '(' : ')';
            }
            const generatedStr = newStr + u_reverse;
            // 4-5. 생성된 문자열을 반환합니다.
            return generatedStr;  
        }
    };
    return recursive(p);
}

function checkCorrectStr(str) {
    const stack = [];

    for (let i = 0; i < str.length; i++) {
        if (str[i] === '(') {
            stack.push('(');
        }
        else {
            if (stack.length > 0) {
                stack.pop();
            }
            else {
                return false;
            }
        }
    }
    return true;
}

function findDivideIndex(str) {
    let left = 0;
    let right = 0;
    let answer = 0;
    
    for (let i = 0; i < str.length; i++) {
        const curStr = str[i];

        curStr === ')' ? right += 1 : left += 1;
        
        if (left !== 0 && right !== 0 && left === right) {
            answer = i;
            break;
        }
    }
    
    return answer;
}

프로그래머스 괄호 변환 JavaScript

문제 풀이

댓글