2020 KAKAO BLIND RECRUITMENT 괄호 변환

본 풀이는 java 언어를 사용하였습니다.
문제 보러가기

풀이

과정을 다시 살펴보면서 하나하나 구현해나가면 쉽게 풀 수 있다.

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. 생성된 문자열을 반환합니다.

문자열을 분리하는 로직을 아래와 같이 만들어 주었다.
u 와 v 를 나타내는 부분을 Text 객체로 만들어서 값을 저장할 수 있도록 하였다.

public String solution(String p) {
    // 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
    if (p.isEmpty()) {
        return p;
    }

    Text u = new Text();
    Text v = new Text();
    separateText(p, u, v);
}

private void separateText(String p, Text u, Text v) {
    StringBuilder sb = new StringBuilder();
    Stack<Character> stack = new Stack<>();
    // ')' 로 시작하는 경우
    if (p.charAt(0) == ')') {
        sb.append(p.charAt(0));
        int openTextCount = 0;
        int closeTextCount = 1;
        for (int i = 1; i < p.length(); i++) {
            char word = p.charAt(i);
            if (word == '(') {
                openTextCount++;
            } else {
                closeTextCount++;
            }
            sb.append(word);
            if (openTextCount == closeTextCount) {
                u.setText(sb.toString());
                v.setText(p.substring(i + 1));
                break;
            }
        }
        return;
    }
    // '(' 로 시작하는 경우
    for (int i = 0; i < p.length(); i++) {
        char word = p.charAt(i);
        if (word == ')') {
            try {
                stack.pop();
            } catch (Exception e) {
                v.setText(p.substring(i));
                break;
            }
        } else if (word == '(') {
            stack.push(word);
        }
        sb.append(word);
    }
    u.setText(sb.toString());
}

위 부분이 살짝 어려울 수 있는데, 첫 문자가 ')' 라면 u 는 올바른 괄호 문자열이 아니게 된다.
따라서 '(' 와 ')' 의 개수가 같을때까지만 문자를 더해준다. 그 외 나머지 문자는 v 가 된다.

만약 첫 문자가 '(' 라면 스택에 값을 넣고 ')' 면 스택의 값을 뺀다.
스택이 비어있는데 ')' 를 만나 pop 을 하게되면 Exception 이 발생하는데 그 문자부터는 v 문자열이라는 말이 된다.
또한, 스택이 비어있다는 말은 u 는 균형잡힌 괄호 문자열이라는 말이 된다.

    ...
    separateText(p, u, v);

    return isProperText(u.getText()) ?
            u.getText() + solution(v.getText())
            : "(" + solution(v.getText()) + ")" + removeAndReverseText(u.getText());
}

separateText 를 수행하면 u 와 v 의 값으로 나뉘게 되는데,
isProperText 메서드를 통해 u 가 올바른 괄호 문자열인지를 체크한다.

u 가 올바른 괄호 문자열이 맞다면, 수행한 결과 문자열을 u에 이어 붙인 후 반환한다.
u 가 올바른 괄호 문자열이 아니라면, 4-1 ~ 4-5 과정을 수행한다.

코드

import java.util.Stack;

public class Solution {

    public String solution(String p) {
        if (p.isEmpty()) {
            return p;
        }

        Text u = new Text();
        Text v = new Text();
        separateText(p, u, v);

        return isProperText(u.getText()) ?
                u.getText() + solution(v.getText())
                : "(" + solution(v.getText()) + ")" + removeAndReverseText(u.getText());
    }

    private void separateText(String p, Text u, Text v) {
        StringBuilder sb = new StringBuilder();
        Stack<Character> stack = new Stack<>();

        // ')' 로 시작하는 경우
        if (p.charAt(0) == ')') {
            sb.append(p.charAt(0));
            int openTextCount = 0;
            int closeTextCount = 1;
            for (int i = 1; i < p.length(); i++) {
                char word = p.charAt(i);
                if (word == '(') {
                    openTextCount++;
                } else {
                    closeTextCount++;
                }
                sb.append(word);
                if (openTextCount == closeTextCount) {
                    u.setText(sb.toString());
                    v.setText(p.substring(i + 1));
                    break;
                }
            }
            return;
        }

        // '(' 로 시작하는 경우
        for (int i = 0; i < p.length(); i++) {
            char word = p.charAt(i);
            if (word == ')') {
                try {
                    stack.pop();
                } catch (Exception e) {
                    v.setText(p.substring(i));
                    break;
                }
            } else if (word == '(') {
                stack.push(word);
            }
            sb.append(word);
        }
        u.setText(sb.toString());
    }

    private boolean isProperText(String u) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < u.length(); i++) {
            char word = u.charAt(i);
            if (word == '(') {
                stack.push(word);
            } else {
                try {
                    stack.pop();
                } catch (Exception e) {
                    return false;
                }
            }
        }
        return true;
    }

    private String removeAndReverseText(String u) {
        u = u.substring(1, u.length() - 1);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < u.length(); i++) {
            char word = u.charAt(i);
            if (word == '(') {
                sb.append(')');
            } else {
                sb.append('(');
            }
        }
        return sb.toString();
    }
}

class Text {

    private String text;

    public Text() {
        text = "";
    }

    public String getText() {
        return text;
    }

    public void setText(String text) {
        this.text = text;
    }
}

회고

재귀로 어떻게 처리해야할지 막막했는데 문제에 정의되어있는 과정을 메서드로 분리하여 하나씩 처리하니까 쉽게 통과되어서 놀랐다.
예전에 2020 카카오 블라인드 코테에서 이 문제를 직접 풀다가 포기했었는데 지금은 시간이 걸리긴했지만 풀리는걸 보니 실력이 늘긴했나보다.