[프로그래머스/Java] 60058번 괄호 변환

프로그래머스 괄호 변환 [2020 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/60058

지문에 풀이가 다 쓰여있는 문제였지만, 읽으면서 '국어문제인가..?'하는 생각이 들었던 것도 사실이다.

의문 없이 풀이를 받아들였다면 아마 금방 풀었을 것이다. 하지만 풀었다고 해도 찝찝함이 남았겠지.
이 방법으로 변환했을 때 왜 올바른 괄호 문자열이 나오는 지 이해하려 들다보니 시간이 필요했던 듯 하다.

알고리즘에 대한 풀이가 무의미한 문제인 만큼, 풀면서 물음표를 던졌던 부분에 대한 해설을 적어보려 한다.

.
.

문제에서 제시한 변환 과정은 다음과 같다.

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
   3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
   4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
   4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
   4-3. ')'를 다시 붙입니다.
   4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
   4-5. 생성된 문자열을 반환합니다.

대부분 1~3번 절차는 무리 없이 받아들였을거라 생각한다. 4번에서 든 의문은 크게 세 가지였다.

1. 왜 '(' + v를 올바른 문자열로 변환한 결과 + ')'를 앞에 붙이는가?
2. 왜 u의 첫번째와 마지막 문자를 제거하는가?
3. 왜 나머지 문자의 괄호 방향을 뒤집어야 하는가?

이 중 1번은 그냥 받아들여야 하는 약속이라고 생각한다. 이것을 u의 앞에 붙이든, 뒤에 붙이든 그 결과가 '올바른 괄호 문자열'이 된다는 것은 변함이 없다. 정답을 정해놓고, 이것을 맞추게 하기 위한 약속일 뿐이다.

u가 '올바른 괄호 문자열'이 아니면서 '더이상 분리할 수 없는 균형잡힌 괄호 문자열'이라는 것은 곧 ')'로 시작해서 '('로 끝난다는 뜻이 된다. 근거는 다음과 같다.

1. '('로 시작하는 더이상 분리할 수 없는 균형잡힌 괄호 문자열은 올바른 괄호문자열이다. 따라서 ')'로 시작해야 한다.
2. ')'로 시작해 ')'로 끝난다면 균형잡힌 괄호 문자열로 더 분리할 수 있다. 따라서 '('로 끝나야 한다.

따라서 2번 절차를 통해 맨 앞의 ')'와 맨 뒤의 '('를 제거하게 되는데, 1번에서 '('과 ')'를 한 번 씩 추가했으므로 전체 괄호 개수에는 변함이 없게 된다.

머리와 꼬리를 떼어넨 u의 길이가 1 이상이라면 또 다시 ')'로 시작할 수 밖에 없는데, 만약 '('로 시작한다면 머리, 꼬리를 떼어내기 전 ")(....("의 형태로 앞의 두 글자로 또 분리할 수 있는 괄호문자열이 되기 때문에 모순이 된다.

따라서 ')'로 시작하는 균형잡힌 괄호 문자열로, 전체 괄호 방향을 뒤집어 올바른 괄호 문자열로 만들 수 있다.

class Solution {
    public String solution(String p) {
        return getRightString(p);
    }
    public String getRightString(String p){
        int parseIndex = getParseIndex(p);
        if(parseIndex < 0) return p;
        else {
            String u = p.substring(0, parseIndex);
            String v = p.substring(parseIndex);
            int uParseIndex = getParseIndex(u);
            if(uParseIndex < 0) return u + getRightString(v);
            return "(" + getRightString(v) + ")" + getReverseString(u.substring(1, u.length()-1));
        }
    }
    public String getReverseString(String p){
        StringBuilder sb = new StringBuilder();
        for(char c : p.toCharArray()){
            if(c == '(') sb.append(")");
            else sb.append("(");
        }
        return sb.toString();
    }
    public int getParseIndex(String p){ // 올바른 괄호 문자열이면 -1을, 아니라면 u와 v를 분리하는 index를 return
        char[] charArr = p.toCharArray();
        boolean rightFlag = true;
        int stackSize = 0, openBracket = 0, closeBracket = 0, resultIndex = -1;
        for(int i = 0 ; i < charArr.length ; i++){
            if(charArr[i] == '('){
                stackSize++;
                openBracket++;
            } else {
                stackSize--;
                closeBracket++;
                if(stackSize < 0) rightFlag = false;
            }
            if(resultIndex < 0 && openBracket == closeBracket) resultIndex = i+1;
        }
        if(rightFlag) return -1;
        return resultIndex;
    }
}