[프로그래머스] Level2 - 괄호 변환(Javascript)

프로그래머스

▶ 문제 요약

1. 여는 괄호("(")와 닫는 괄호(")")의 개수가 같다면 균형잡힌 괄호 문자열, 괄호의 짝도 맞다면 올바른 괄호 문자열이라고 부른다.

2. 올바른 괄호 문자열이 아닌 경우 올바른 괄호 문자열로 변환하는 과정을 거치게 된다. 

3. 입력이 빈 문자열인 경우, 빈 문자열을 반환한다.

4. 문자열 w를 u,v 로 분리한다. 나누는 기준은 여는 괄호와 닫는 괄호의 개수가 같아지는 지점으로해서 같아지는 부분까지 u 아니면 v

5. 문자열 u가 올바른 괄호 문자열이면 u에 재귀(v) 를 붙인다.

6. 올바른 괄호 문자열이 아니라면 "(" + 재귀(v) + ")" + u의 첫 번째와 마지막 문자 제거 및 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙인다.

7. 생성된 문자열을 반환한다.

 

 

▶ 정답 코드

// 괄호짝이 맞는지 확인
function check(string) {
    let stack = [];
    
    // 만약 s가 여는 괄호면 배열에 담고
    for (const s of string) {
        if (s === "(") {
           stack.push("(");
        // 닫는 괄호이면   
        } else {
           // 만약에 stack이 없는 경우에 false
           if (stack.length === 0) {
               return false;
           // 있으면 배열에서 제거해준다.    
           } else {
               stack.pop();
           }
        }
    }
    
    // boolean 형식으로 배열의 크기가 0인지를 확인
    return stack.length === 0;

}

// 괄호 방향 뒤집는 함수
function reverse(string) {
    let reversed = "";
    
    // 여는 괄호면 닫는 괄호로 바꾸고
    // 닫는 괄호면 여는 괄호로 바꾼다. 
    for (const s of string) {
        if (s === "(") reversed += ")";
        else reversed += "(";
    }
    
    return reversed;

}

function solution(p) {
    
    let left = 0, right = 0, u = 0, v = 0;
    
    // 입력이 빈 문자일 경우 빈 문자열 반환
    if (p === "") return "";
    
    
    // 여는 괄호, 닫는 괄호 세주기
    for (let i = 0; i < p.length; i++) {
        if (p[i] === "(") left++;
        else right++;
        
        // 개수가 같아지는 지점에서
        if (left === right) {
            // 같아지는 지점까지 u에 담고
            u = p.slice(0, i+1);
            // 나머지는 v에 담는다.
            v = p.slice(i+1);
            break;
        }
    }
    
    // 만약 u가 올바른 괄호 문자열이면
    if (check(u)) {
       // 기존 u + 재귀로 v를 다시 돌려준다.
       return u + solution(v);
    } else {
       // 올바른 괄호 문자열이 아니면
       // 여는 괄호 + 재귀(v) + 닫는 괄호 + 첫 번째, 마지막 문자열 제거 및 괄호 방향 뒤집기
       return "(" + solution(v) + ")" + reverse(u.slice(1, u.length -1));
    }
    
    
    
    



}

 

▶ 풀이 과정

1.  처음에 올바른 괄호 문자열인지 확인하는 함수를 만들었다. 첫 번째 함수에서는 boolean을 활용해서 올바른 괄호 문자열인 경우 true 아닌 경우 false를 출력할 수 있게 처리했는데, 여기서 코드를 구성할 때 실수한 부분이 배열이 비었을 때 처리하는 것을 미쳐 생각하지 못했다. 여는 괄호면 stack에 추가 닫는 괄호면 stack에서 제거하는 방식으로 올바른 괄호 문자열인지 체크했다.

 

2. 두 번째 함수는 괄호 방향 뒤집는 함수이다. 문제에서 4-4의 나머지 문자열의 괄호 방향을 뒤집어야 하는 부분을 만족시키기 위해 간단하게 만들었다. 여는 괄호면 변수에 닫는 괄호를 더하고 닫는 괄호면 여는 괄호를 더한다. 

 

3. 본 함수에서는 입력이 빈 문자열일 경우 빈 문자열을 반환하라는 요구에 맞췄다. 그리고 입력값 p를 u, v로 나눠야 하는데 기준은 여는 괄호와 닫는 괄호의 개수가 같아지는 지점에서 u와 v를 나눈다. 같아지는 지점까지 u에 넣고 나머지는 v에 넣는다. 

 

4. 문자열 u가 올바른 괄호 문자열이면 기존 u + 재귀(v)해서 값을 리턴하고 아니면 여는 괄호 + 재귀(v) + 닫는 괄호 + 첫 번째, 마지막 문자열을 제거(slice활용) 및 괄호 방향 뒤집는 건 위에서 만든 함수를 활용했다. 

 

 

▶ 느낀점

- 난이도가 높아지는만큼 항상 예외사항을 고려해서 설계해야한다. 

 

- 재귀에 너무 겁을 먹는다... 재귀 공부를 더하자.