[Algorithm] 괄호 변환

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

 

풀이

먼저, 해당 문제는 시키는대로 잘 따라가면 된다.

 

순서대로 진행하는데, 균형잡힌 문자열과 올바른 문자열에 대해서 어떻게 판단할 것인지 생각해야한다.

균형 잡힌 문자열은 개수가 같은 것이기 때문에 '(' 와 ')'의 갯수가 동일한 경우의 index를 반환한다.

올바른 문자열은 '('와 ')'의 균형이 맞으면서 순서도 맞아야 한다. ')'이 먼저 나오는 경우 안된다.

 

나머지 부분은 문제에 정의된 부분대로 구현하면 되었다.

class Solution {
    
    public int findIndex(String p) {
        int cnt = 0;
        for (int i = 0; i < p.length(); i++) {
            if (p.charAt(i) == '(') cnt++;
            else cnt--;
            if (cnt == 0) return i;
        }
        return -1;
    }
    
    public boolean check(String p) {
        int cnt = 0;
        for (int i = 0; i < p.length(); i++) {
            if (p.charAt(i) == '(') cnt++;
            else {
                if (cnt == 0) return false;
                cnt--;
            }
        }
        return true;
    }
    
    public String solution(String p) {
        String answer = "";
        
        if (p.equals("")) return answer;
        int index = findIndex(p);
        String u = p.substring(0, index+1);
        String v = p.substring(index+1);
        
        if (check(u)) {
            answer = u + solution(v);
        } else {
            answer = "(";
            answer += solution(v);
            answer += ")";
            u = u.substring(1, u.length() - 1);
            String tmp = "";
            for (int i = 0; i < u.length(); i++) {
                if (u.charAt(i) == '(') tmp += ')';
                else tmp += '(';
            }
            answer += tmp;
        }
        
        
        return answer;
    }
}