[JS] 2020카카오 : 괄호 변환 프로그래머스 LEVEL2

---

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/60058

풀이 전략

p는 '(' 와 ')' 로만 이루어진 문자열이며 길이는 2 이상 1,000 이하인 짝수입니다.
문자열 p를 이루는 '(' 와 ')' 의 개수는 항상 같습니다.
만약 p가 이미 "올바른 괄호 문자열"이라면 그대로 return 하면 됩니다.

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 solution(p) {
    let answer;

    if (isProper(p)) return p;
    else answer = dfs(p);

    return answer;
}

function dfs(str) {
    if (str === "") return str;
    const [u, v] = makeUV(str);

    if (isProper(u)) return u + dfs(v);
    else return "(" + dfs(v) + ")" + reverseBracket(u.slice(1, -1));
}

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

    for (const bracket of str) {
        if (bracket === "(") stack.push(bracket);
        else {
            const elem = stack.pop();
            if (elem === undefined) return false;
        }
    }
    if (stack.length) return false;
    else return true;
}

function makeUV(str) {
    const stack = [];
    let i = 1;
    let u = "";
    let v = "";

    stack.push(str[0]);
    u += str[0];
    while (i < str.length) {
        if (stack.length === 0) break;
        const bracket = str[i];
        const prev = stack[stack.length - 1];
        if (prev === bracket) stack.push(bracket);
        else stack.pop();

        u += bracket;
        i++;
    }
    v = str.slice(i);
    return [u, v];
}

function reverseBracket(str) {
    let tmp = "";

    for (const bracket of str) {
        if (bracket === ")") tmp += "(";
        else tmp += ")";
    }

    return tmp;
}

 

회고

막상 문제를 풀고 다른 분들의 풀이를 확인하니. 다양한 방법으로 기발하게 푸신분들이 많아서 아직 실력을 더 키워야 겠다고 생각하였다. 나는 주어진 문제를 읽고 그대로"구현"에만 집중하였다면, 이제는 그 문제를 조금 더 쉽게 공략? 할 수 있는 방법을 생각해야겠다. 

 

더 좋은 방법이나 의견이 있으시다면 댓글 부탁드립니다 :)