[프로그래머스] 60058. 괄호 변환

문제 링크

[프로그래머스] 60058. 괄호 변환

풀이 과정

문제에서 주어진 아래 규칙에 맞게 코드를 작성하는 구현 문제입니다.

static String divide(String p) {
        if (p.length() == 0) return "";

        int endIdx = getEndIdx(p) + 1;
        String u = p.substring(0, endIdx);
        String v = p.substring(endIdx);

        if (isRight(u)) {
            return u + divide(v);
        } else {
            StringBuilder tmp = new StringBuilder("(");
            tmp.append(divide(v));
            tmp.append(")");

            for (int i = 1; i < u.length() - 1; i++) {
                if (u.charAt(i) == '(') tmp.append(")");
                else tmp.append("(");
            }

            return tmp.toString();
        }
    }

divide 메소드는 위의 규칙을 그대로 수행합니다. 먼저 getEndIdx 메소드를 통해 문자열 u가 끝나는 지점의 인덱스를 받아와, 파라미터 p 를 u 와 v 로 나눕니다. 다음으로, isRight 메소드를 통해 문자열 u 가 균형잡힌 문자열인지 아닌지에 따라 다르게 동작합니다.

static int getEndIdx(String p) {
    int left = 0, right = 0, idx = 0;

    while (idx < p.length()) {
        if (p.charAt(idx) == '(') left++;
        else if (p.charAt(idx) == ')') right++;

        if (left == right) break;

        idx++;
    }

    return idx;
}

getEndIdx 메소드는 문자열 p에서 u와 v의 경계를 구하는 작업을 수행합니다. 왼쪽 괄호와 오른쪽 괄호의 개수를 세어, 그 값이 같아지는 시점의 인덱스를 리턴합니다.

static boolean isRight(String u) {
    Stack<Character> stack = new Stack<>();

    for (int i = 0; i < u.length(); i++) {
        if (u.charAt(i) == '(') stack.push('(');
        else if (!stack.isEmpty()) stack.pop();
    }

    return stack.isEmpty() ? true : false;
}

isRight 메소드는 스택을 사용해, 문자열 u 가 균형잡힌 문자열인지 아닌지를 확인합니다.

코드

import java.util.Stack;

public class Main {
    public static String solution(String p) {
        String answer = divide(p);

        return answer;
    }

    static String divide(String p) {
        if (p.length() == 0) return "";

        int endIdx = getEndIdx(p) + 1;
        String u = p.substring(0, endIdx);
        String v = p.substring(endIdx);

        if (isRight(u)) {
            return u + divide(v);
        } else {
            StringBuilder tmp = new StringBuilder("(");
            tmp.append(divide(v));
            tmp.append(")");

            for (int i = 1; i < u.length() - 1; i++) {
                if (u.charAt(i) == '(') tmp.append(")");
                else tmp.append("(");
            }

            return tmp.toString();
        }
    }

    static int getEndIdx(String p) {
        int left = 0, right = 0, idx = 0;

        while (idx < p.length()) {
            if (p.charAt(idx) == '(') left++;
            else if (p.charAt(idx) == ')') right++;

            if (left == right) break;

            idx++;
        }

        return idx;
    }

    static boolean isRight(String u) {
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < u.length(); i++) {
            if (u.charAt(i) == '(') stack.push('(');
            else if (!stack.isEmpty()) stack.pop();
        }

        return stack.isEmpty() ? true : false;
    }

    public static void main(String[] args) {
        solution("(()())()");
//        solution(")(");
//        solution("()))((()");
    }
}