문제 링크

문제 간단 해석

균형잡힌 괄호 문자열 두 개로 쪼갠 뒤, 올바른 괄호 문자열인지에 따라 처리를 하는 문제.

Java

StringBuilder와 재귀를 사용했다.

풀이 코드

class Solution {
    public String cut(String s) {
        StringBuilder sb = new StringBuilder();
        s = s.substring(1, s.length() - 1);

        for(int i = 0; i < s.length(); i++)
            sb.append(s.charAt(i) == '(' ? ')' : '(');

        return sb.toString();
    }

    public String solution(String p) {
        int i = 0, score = 0;
        boolean flag = true;
        StringBuilder sb = new StringBuilder();

        if (p.length() == 0)
            return "";

        do {
            score += p.charAt(i) == '(' ? 1 : -1;
            i++;

            if (score < 0)
                flag = false;

        } while (score != 0);


        if (flag)
            return sb
                .append(p.substring(0, i))
                .append(
                    solution(p.substring(i)))
                .toString();

        return sb
            .append('(')
            .append(
                solution(p.substring(i)))
            .append(')')
            .append(
                cut(p.substring(0, i)))
            .toString();
    }
}

해석

if (p.length() == 0)
    return "";

do {
    score += p.charAt(i) == '(' ? 1 : -1;
    i++;

    if (score < 0)
        flag = false;

} while (score != 0);

재귀 도중 p가 빈 문자열이 들어올 수 있으므로, 빈 문자열 그대로 반환하도록 했다.

만약 (이 들어왔을 경우 괄호의 시작이므로 score에 1을 증가, )이라면 1을 감소하도록 했다.

만약 score가 음수라면, 해당하는 괄호 문자열은 올바르지 않은 괄호열이다. 따라서 flag에 false를 주었다.

만약 score가 0이 되어 균형잡힌 괄호 문자열이 된 경우 멈추도록 했다.

if (flag)
    return sb
    .append(p.substring(0, i))
    .append(
    	solution(p.substring(i)))
    .toString();

옳은 문자열이라면, 방금 찾아낸 옳은 문자열과 그 이후의 문자열을 판단한 결과를 더해 반환해준다.
이후의 문자열은 재귀로 돌린다.

return sb
    .append('(')
    .append(
    	solution(p.substring(i)))
    .append(')')
    .append(
    	cut(p.substring(0, i)))
    .toString();

옳지 않은 문자열이라면, ( + 이후의 문자열 판단 결과 + ) + cut(옳지 않은 문자열)을 반환하도록 했다.

public String cut(String s) {
    StringBuilder sb = new StringBuilder();
    s = s.substring(1, s.length() - 1);

    for(int i = 0; i < s.length(); i++)
        sb.append(s.charAt(i) == '(' ? ')' : '(');

    return sb.toString();
}

cut은 문자열의 앞뒤를 자르고, 내부 괄호를 반대로 바꾸는 작업을 한다.
앞뒤를 자른 후 괄호의 반댓값을 StringBuilder에 차곡차곡 넣어준 후 반환한다.

Python

풀이 코드

def CutAndReverse(p):
    str = list(p[1:-1])
    for i in range(len(str)):
        str[i] = ')' if str[i] == '(' else '('
    return "".join(str)

def solution(p):
    if p == "":
        return p

    status = 0
    flag = True

    i = 0
    for i in range(len(p)):
        if p[i] == '(':
            status += 1
        else:
            status -= 1
        if status < 0:
            flag = False
        if status == 0:
            break

    u = p[:i + 1]
    v = p[i + 1:]
    str = ""

    if flag:
        str += u + solution(v)
    else:
        str += '(' + solution(v) + ')' + CutAndReverse(u)

    return str

해석

Java와 같음.