오늘 풀어본 문제는
프로그래머스 괄호변환 입니다.

📕 문제 링크

❗️코드

import java.util.*;
class Solution {
    static StringBuilder sb;
    public String solution(String p) {
        if(p.equals("")) return "";
        StringBuilder sb = new StringBuilder();
        sb.append(make(p));
        return sb.toString();
    }
    static String make(String str) // ))((  ()
    {
        if(str.length() == 0) return "";
        String [] sep = separate(str);
        String u = sep[0], v = sep[1]; // (()()) , ()
        if(isCorrect(u))
        {
            return u + make(v);
        }
        else
        {
            StringBuilder tmp = new StringBuilder();
            tmp.append("(").append(make(v)).append(")");
            String tmpU = u.substring(1,u.length()-1);
            tmpU = reverse(tmpU);
            tmp.append(tmpU);
            return tmp.toString();
        }
    }
    static String [] separate(String str)
    {
        String [] arr = new String[2];
        int left = 0, right = 0,end = 0;
        for(int i = 0; i < str.length(); ++i)
        {
            String tmp = str.charAt(i)+"";
            if(tmp.equals("(")) left++;
            else right++;
            if(left == right)
            {
                end = i;
                break;
            }
        }
        arr[0] = str.substring(0,end+1);
        arr[1] = str.substring(end+1);

        return arr;
    }
    static boolean isCorrect(String str)
    {
        if(str.length() ==0) return false;
        int cnt = 0; //())
        for(int i = 0; i < str.length(); ++i)
        {
            String tmp = str.charAt(i)+"";
            if(tmp.equals("(")) cnt++;
            else cnt--;
            if(cnt < 0) return false;
        }
        return true;
    }
    static String reverse(String str)
    {
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < str.length(); ++i)
        {
            String cur = str.charAt(i)+"";
            if(cur.equals("(")) sb.append(")");
            else sb.append("(");
        }
        return sb.toString();
    }
}

📝 풀이

재귀를 사용하여 괄호를 올바르게 정리해주는 문제입니다.
먼저 문자열을 조건에 맞게 두개로 분리하고, u가 올바른 괄호 문자열인지 확인해줍니다.
문자열을 분리하는 separate함수에서 이미 양쪽 괄호 갯수가 맞게 정리된 문자열이므로,
u 문자열이 올바른지 확인하는 함수에서는 괄호가 열린만큼 닫힌지만 확인해주면 됩니다. 따라서 왼괄호 '(' 가 나왔을때는 카운트를 ++ , 오른괄호 ')' 일때는 카운트를 -- 해주고, 카운트값이 음수가 되는 순간 괄호가 열린 카운트보다 닫힌 카운트가 많아지는 상태이기때문에, 적합하지 않다고 판단할 수 있습니다. 오른괄호로 시작하는 문자열도 마찬가지로 시작하자마자 카운트가 -1이므로 false를 리턴하게 됩니다.
이렇게 u가 올바른 문자열인지 확인했으면, 여부에따라 u를 바로 StringBuilder에 합치거나, 주어진 조건에 맞게 u와 v를 재귀호출하여 문자열을 완성할 수 있습니다.

📜 후기

오늘도 코딩테스트를 대비하여 기출문제를 풀어보았습니다!
문제를 이해하는게 조금 힘들었지만, 주어진 조건 순서대로 그냥 짜다보니 해결되었습니다. 문제가 헷갈릴땐 시간 허비하지 말고 일단 짜봐야겠어요..ㅋㅋㅋㅋㅋ