[프로그래머스] 괄호 변환

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

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

2020 KAKAO BLIND RECRUITMENT

LEVEL 2

문제설명

'(', ')'로만 이루어진 문자열 p가 주어졌을 때 다음 알고리즘을 수행해 "올바른 괄호 문자열"로 변환한 결과를 return하는 solution함수를 작성하시오,

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

INPUT

p

• '(', ')'로만 이루어진 문자열
• 2 ≤ p의 길이 ≤ 1,000
• 문자열 p를 이루는 '('와 ')'의 개수는 항상 같다. (문자열 p의 길이는 짝수)

OUTPUT

• 변환 알고리즘을 거친 문자열
• 입력이 이미 "올바른 괄호 문자열"일 경우 그대로 반환합니다.

나의 풀이

• 이미 구현할 알고리즘에 대한 설명이 주어져서 주어진 그대로 구현하기만 하면 된다.

function solution(p) {
    // splitInTwo: 주어진 알고리즘을 실행하여 문자열을 변환하는 재귀함수
    function splitInTwo(w) {
        // 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환
        if (w === '') return '';
      
        // 2. 문자열 w를 균형잡힌 괄호 문자열 u, v로 분리
        let u, v;
        let count = 0;
        for (let i = 0, n = w.length; i < n; i++) {
            (w[i] === '(') ? count++ : count--;
            if (count === 0) {
                u = w.slice(0, i+1);
                v = w.slice(i+1);
                break;
            }
        }
        
        if (isCorrectString(u)) {
            // 3. u가 올바른 괄호 문자열일 경우,
            return u + splitInTwo(v);
        } else {
            // 4. u가 올바른 괄호 문자열이 아닐 경우,
            let v2 = '(' + splitInTwo(v) + ')';
            let u2 = u.split('').slice(1, -1).map(el => {
                return (el === '(') ? ')' : '('
            }).join('');
            return v2 + u2;
        }
    }
  
    // isCorrectString: 주어진 문자 u가 올바른 괄호 문자열인지 참/거짓 여부를 반환하는 함수
    function isCorrectString(u) {
        const stack = [];
        for (let i = 0, n = u.length; i < n; i++) {
            if (u[i] === '(') {
                stack.push('(');
            } else {
                const match = stack.pop();
                if (match !== '(') return false;
            }
        }
        return (stack.length === 0) ? true : false;
    }
  
    // splitInTow에 p를 대입한 결과를 반환
    return splitInTwo(p);
}