[코딩테스트 + Java] 괄호 변환 - 프로그래머스 Lv.2

🔗 문제 링크

프로그래머스 60058 - 괄호 변환

---

🧠 문제 설명

• 입력 문자열 p는 균형잡힌 괄호 문자열 (열림/닫힘 개수만 같음)
• 이를 "올바른 괄호 문자열"로 변환해야 함
• 주어진 알고리즘 조건(1~5단계)을 코드로 구현

---

📌 핵심 개념

용어	의미
균형잡힌 괄호 문자열	'('와 ')'의 개수가 같음
올바른 괄호 문자열	열리고(() 나서 닫힘()) 순서가 올바름
재귀	문자열을 u와 v로 분리하여 재귀적으로 처리

---

🔄 알고리즘 요약

1. 입력이 빈 문자열 → 빈 문자열 반환
2. p를 "균형잡힌 u"와 나머지 v로 분리
3. u가 올바른 괄호면 → u + solution(v)
4. 아니라면 → "(" + solution(v) + ")" + u의 앞뒤 제거 후 괄호 뒤집기"

---

✅ 코드 구현

public String solution(String p) {
            String answer = "";
            // 빈 문자열인 경우, 빈 문자열 반환
            if (p.length() == 0) return "";
            // string의 길이가 2일 경우 올바른 괄호 문자열은 () 밖에 없으므로 () 반환
            else if (p.length() == 2) return "()";

            // u가 끝나는 index
            int start = 0;
            // 괄호가 제대로 닫혔는지 확인하는 변수
            int count = 0;
            // 균형잡힌 괄호 문자열 u가 올바른 괄호 문자열인지 확인하는 변수
            boolean isRight = true;

            // 균형잡힌 문자열 p를 u와 v로 나누는 로직
            for (int i = 0; i<p.length(); i++){
                count += p.charAt(i) == '(' ? 1 : -1;
                // count가 음수로 한번이라도 변경되면 올바른 괄호 문자열이 아님.
                if (count < 0) isRight = false;

                // count가 0이 되면 괄호의 열림과 닫힘이 짝이 맞음
                // 균형잡힌 괄호 문자열임.
                if (count == 0){
                    start = i+1;
                    answer += p.substring(0, start);
                    break;
                }
            }
            // 반복문을 모두 돌았는데 균형잡힌 문자열이 아닌 경우 u의 값을 문자열 전체로 지정
            if (count != 0) {
                start = p.length();
                answer += p.substring(0, start);
            }

            // p에서 u를 제외한 문자열 v를 재귀함수를 통해 반환
            String v = solution(p.substring(start));
            // 수행한 결과를 문자열 u에 이어 붙임
            answer+=v;

            // 문자열 u가 올바른 괄호 문자열이 아닌 경우 로직에 따라 processU 진행
            if (!isRight) {
                return processU(p.substring(0, start), v);
            }

            // 최종 결과 answer 반환
            return answer;
        }

---

💡 포인트 설명

• count < 0 체크는 올바른 괄호 판단용 (스택 대신 간단 처리)
• substring(1, u.length()-1) → 앞뒤 괄호 제거
• 괄호 반전은 '(' → ')', ')' → '('
• StringBuilder를 쓰면 성능도 향상 가능

---

🧪 예시 테스트

public static void main(String[] args) {
        // 정상 결과: [2, 1]
        System.out.println(Arrays.toString(solution(new int[]{93, 30, 55}, new int[]{1, 30, 5})));
        // 정상 결과: [1, 3, 2]
        System.out.println(Arrays.toString(solution(new int[]{95, 90, 99, 99, 80, 99}, new int[]{1, 1, 1, 1, 1, 1})));
        // 정상 결과: [1, 1]
        System.out.println(Arrays.toString(solution(new int[]{90, 90}, new int[]{10, 9})));
    }

---

🧩 회고

• 재귀 기반 문제 중 로직 분기 조건이 많은 편
• 문자열을 나누는 기준과 isRight 판단 순서를 실수하기 쉬움
• 괄호 유효성 검사는 스택 없이도 count만으로 가능하다는 점이 핵심