[프로그래머스/자바] 괄호 변환 풀이 - 2020 KAKAO BLIND RECRUITMENT

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

프로그래머스

 

2020 KAKAO BLIND RECRUITMENT Level 2 문제다.

 

 

 

먼저 Stack을 통해 문자열 p가 올바른 괄호 문자열인지 판단한다. (isCorrect 함수를 통해)

만약 올바른 괄호 문자열이라면 p를 그대로 반환하고,

올바른 괄호 문자열이 아니라면 올바른 괄호 문자열로 변환하는 setBracket 함수로 변환한 값을 반환한다.

 

문제에 나와있는 과정에 따라 문자열을 u, v로 분리한다.

u가 올바른 괄호 문자열이라면 v를 setBracket 함수에 전달하여 올바른 괄호 문자열으로 바꾼 값과 합친다. (과정 3)

 

u가 올바른 괄호 문자열이 아니라면 빈 문자열에 "(" + setBracket(v) + ")" 를 이어 붙인다.

그리고 u의 앞뒤 한글자씩 삭제하고, 모든 괄호를 반대로 돌려 문자열에 다시 이어붙인다. (과정 4)

 

 

균형잡힌 괄호 문자열을 올바른 괄호 문자열로 변환하는 과정이

문제에 자세히 나와있기 때문에 어렵지 않게 풀 수 있었다.

 

 

주의할점

다만 문제 내의 과정 중에서 2번이 가장 헷갈렸다.

 

2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.

 

여기서 어떤 기준으로 분리하라는 건지 잘 이해가 안 갔다.

u가 균형잡힌 괄호 문자열로 더 이상 분리할 수 없어야 한다.

균형잡힌 괄호 문자열은 "("와 ")"갯수가 같아야 한다.

더이상 분리할 수 없다는 의미는 u에서 "("와 ")"의 갯수가 같은게 두 쌍이 나오면 안된다는 의미와 같다.

"(())()" 처럼 "(())"와 "()"로 "("와 ")"의 갯수가 같은게 두쌍이 나오면, 균형잡힌 괄호 문자열로 또다시 분리가 가능하기 때문이다.

 

즉, "("와 ")"의 갯수가 처음으로 같아지는 곳을 찾으면

"("와 ")"갯수가 같은 게 한쌍이 되는 것이고, 여기서는 더 분리할 수 없다.

separate 함수를 만들어 분리할 기준이 되는 인덱스를 반환했다.

 

 

import java.util.*;

class Solution {
    public String solution(String p) {
        if(isCorrect(p))
            return p;
        return setBracket(p);
    }
    
    static String setBracket(String w) {
        // 1.
        if(w.equals(""))
            return w;
        
        // 2.
        int idx = separate(w);
        StringBuilder u = new StringBuilder(w.substring(0, idx + 1));
        StringBuilder v = new StringBuilder(w.substring(idx + 1, w.length()));
        StringBuilder sb = new StringBuilder();
        
        // 3.
        if(isCorrect(u.toString())) 
            // 3-1.
            sb.append(u).append(setBracket(v.toString()));
        // 4.
        else {
            // 4-1. 4-2. 4-3.
            sb.append('(').append(setBracket(v.toString())).append(')');
            // 4-4.
            u.deleteCharAt(u.length() - 1);
            u.deleteCharAt(0);
            for(int i=0;i<u.length();i++) {
                char c = u.charAt(i);
                if(c == '(')
                    u.setCharAt(i, ')');
                else
                    u.setCharAt(i, '(');
            }
            sb.append(u);
        }
        
        return sb.toString();
    }
    
    // 올바른 괄호 문자열이라면 0을, 아니라면 u, v로 분리할 인덱스 반환
    static boolean isCorrect(String s) {
        Stack<Character> stack = new Stack<>();
        
        for(int i=0;i<s.length();i++) {
            char c = s.charAt(i);
            if(c == '(')
                stack.push(c);
            else if(c == ')') {
                if(stack.empty()) 
                    return false;
                else
                    stack.pop();
            }
        }
        
        return stack.empty() ? true : false;
    }
    
    static int separate(String s) {
        int open = 0;
        int close = 0;
        int ret = 0;
        
        for(int i=0;i<s.length();i++) {
            char c = s.charAt(i);
            if(c == '(')
                open++;
            else if(c == ')')
                close++;
            // 여는 괄호와 닫는 괄호의 갯수가 처음으로 같아질 때를 기준으로 u, v 분리
            if(open == close) {
                ret = i;
                break;
            }
        }
        
        return ret;
    }
}