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

문제

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

프로그래머스

 

 

 

 

풀이

1. 빈 문자열이면 그대로 반환.
2. p를 균형잡힌 괄호 문자열 u와 v로 분리.
3. u가 올바른 괄호 문자열이면, v를 재귀적으로 변환 후 u + solution(v) 반환.
4. u가 올바른 문자열이 아니라면
   • ( 를 추가하고 solution(v) 결과를 붙이고 ) 추가.
   • u의 앞뒤 문자를 제거하고 괄호 방향을 반대로 변환하여 붙임.
   • 변환된 문자열을 반환.

 

class Solution {
    // 균형잡힌 문자열의 인덱스 반환
    public int balancedIndex(String p) {
        int count = 0;  // 왼쪽 괄호 개수
        for (int i = 0; i < p.length(); i++) {
            if(p.charAt(i) == '(') count += 1;
            else count -= 1;
            if(count == 0) return i;
            // '('와 ')'의 개수가 같아지면 균형잡힌 부분 문자열(u)의 끝 인덱스를 반환
        }
        return -1;
    }

    // 올바른 괄호 문자열인지 판단
    public boolean checkProper(String p) {
        int count = 0;  // 왼쪽 괄호 개수
        for (int i = 0; i < p.length(); i++) {
            if(p.charAt(i) == '(') count += 1;
            else {
                if(count == 0) {    // 쌍이 맞지 않는 경우
                    return false;
                }
                count -= 1;
            }
        }
        return true;    // 쌍이 맞는 경우
    }

    public String solution(String p) {
        String answer = "";
        
        // 1. 입력이 빈 문자열이면 그대로 반환
        if(p.isEmpty()) return answer;
        
        // 2. 문자열을 균형잡힌 두 개의 부분 문자열 u, v로 분리
        int index = balancedIndex(p);
        String u = p.substring(0, index + 1);
        String v = p.substring(index + 1);
        
        // 3. u가 올바른 괄호 문자열이라면
        if (checkProper(u)) {
            // v에 대해 solution을 재귀적으로 수행하여 결과를 붙여 반환
            answer = u + solution(v);
        }
        // 4. u가 올바른 괄호 문자열이 아니라면
        else {
            answer = "(";   // 4-1. 빈 문자열에 '(' 추가
            answer += solution(v);  // 4-2. v를 solution 함수로 변환한 결과를 추가
            answer += ")";  // 4-3. ')' 추가
            
            // 4-4. u의 첫 번째와 마지막 문자를 제거하고 나머지 괄호 방향을 뒤집음
            u = u.substring(1, u.length() - 1); // 첫 번째와 마지막 문자를 제거
            StringBuilder temp = new StringBuilder();
            for (int i = 0; i < u.length(); i++) {
                // '('이면 ')'으로, ')'이면 '('으로 변환
                if(u.charAt(i) == '(') temp.append(")");
                else temp.append("(");
            }
            answer += temp; // 변환한 문자열을 뒤에 추가
        }
        // 4-5. 생성된 문자열 반환
        return answer;
    }
}