프로그래머스 - 괄호변환

프로그래머스 - 괄호변환

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

2021/04/15

문제 접근 방법

helper함수

'더이상 쪼갤 수 없는 균형잡힌 문자열'과 '남은 문자열'로 나누는 함수를 만든다.
'(' 와 ')' 의 수가 같다면 균형잡힌 문자열이다.

올바른 괄호 문자열

올바른 괄호 문자열인지 검증해야 한다.
이어진 괄호를 반복적으로 제거하여
남은 괄호가 있는지 확인하다.

완성된 solution

function solution(p) {
    if (p === '') return '';
    let [u, v] = helper(p); // u = 균형잡힌 문자열, v = 남은 문자열
    if (isPerfect(u)) return u + solution(v);
    else {
        // u의 가장 앞/뒤 문자를 제거하고 괄호를 뒤집는다.
        u = u.slice(1, u.length - 1).replace(/(\()|(\))/g, (val) => val === '(' ? ')' : '(')
        return `(${solution(v)})${u}`;
    }
}




function helper(w) { // 더이상 쪼갤 수 없는 균형잡힌 문자열과 남은 문자열로 쪼갠다.
    let u = '', v = '', count = 0;
    for (let i = 0; i < w.length; i++) { // 최초 1회 실행시 count는 0이 아니게 된다.
        if (w[i] === '(') count += 1;
        else count -= 1;
        u += w[i];
        if (!count) break; // count가 0이 되면 최소단위의 균형잡힌 문자열이다.
    }
    v = w.slice(u.length); // 남은 문자열
    return [u, v];
}

function isPerfect(u) { // 올바른 괄호 문자열인지 확인
    let temp = u.length;
    while (u.length > 0) {
        // 괄호가 연속적으로 열리고 닫히면 해당 괄호를 제거한다.
        // ex) (()()) -> ()
        u = u.replace(/\(\)/g, '')
        // 글자수에 변함이 없다면 더이상 연속적이게 열리고 닫힌 괄호는 없다.
        if (temp === u.length) break;
        temp = u.length
    }
    // 올바른 괄호 문자열이었다면 모두 제거되어 문자열 길이가 0이다.
    return u.length ? false : true;
}

균형잡힌 문자열 취득 방법

문자열을 순회하며 '('는 +1, ')'는 -1을 가중치로
매 순회 마지막 단락에서 변수의 상태를 확인한다.
최초로 0이 될 경우 최소 단위의 균형잡힌 문자열이다.

올바른 괄호 문자열인지 확인하는 방법

해당 문자열 길이가 0이 될 때까지
반복적으로 연속된 괄호(열린뒤 바로 닫히는 괄호)를 제거한다.
중간에 문자열의 길이 변화가 없다면 올바르지 않은 괄호 문자열이다.

아쉬웠던점

올바른 문자열의 검증

과연 이렇게 느리고 비효율적인(매우 깊게 중첩된 괄호라면 그 깊이를 전부 반복해야 한다.) 방법으로
올바른 괄호 문자열을 검증해야 했었나..?

아니었다. 꼭 이런 것은 다 완료한 후에야 보인다... ㅠㅠ

균형잡힌 문자열이 올바른 문자열인지 검증하는 것인데
이미 여는 괄호 '('로 시작하는 균형잡힌 문자열은 모두 올바른 문자열이었다.
즉, 필요없는 과정을 반복하고 있었던것...


필요한 기능을 구현하기 전에
그게 정말 필요한 기능인지 생각해보자.