Lv 2-かっこの変換

0、問題

文字列が「(」と「)」のみで構成され、「(」の数と「)」の数が同じである場合は、バランスカッコ文字列と呼ばれます.
「(」と「)」のカッコが一致している場合は、正しいカッコ文字列と呼ばれます.
バランスカッコ文字列pをパラメータとして指定した場合、解関数を完了し、指定したアルゴリズムを実行し、正しいカッコ文字列に変換した結果を返します.
詳しい問題はここで...

1.解答

class Solution {
    // 반복
    static String replay(String u, int count, int repeat) {
        String s = u.replace("()", "");
        count++;
        if(count==repeat) {
            return s;
        }
        return replay(s, count, repeat);
    }
    
    // 올바른 문자열인지 체크
    static boolean check(String u) {
        int count = 0;
        int repeat = u.length()/2;
        String s = replay(u, count, repeat);
        return s.equals("") ? true : false;
    }
    
    // 균형 문자열 나누기
    static String[] balance(String q) {
        String result[] = new String[2];
        int left = 0;
        int right = 0;
        for(int i=0; i<q.length(); i++) {
            if(q.charAt(i)=='(') {
                left++;
            }
            else {
                right++;
            }
            if(left==right) {
                result[0] = q.substring(0, left+right);
                result[1] = q.substring(left+right, q.length());
                break;
            }
        }
        return result;
    }
    
    // 괄호 방향 바꾸기
    static String reverse(String u) {
        StringBuilder result = new StringBuilder();
        for(int i=0; i<u.length(); i++) {
            if(u.charAt(i)=='(') {
                result.append(')');
            }
            else if(u.charAt(i)==')') {
                result.append('(');
            }
        }
        
        return result.toString();
    }
    
    // 문자열 교정하는 메인 함수
    static String correct(String p) {
        String answer = "";
        if(p==null) {
            return p;
        }
        
        String u = balance(p)[0];
        String v = balance(p)[1];
        
        if(u==null) {
        	return "";
        }
        boolean isCorrect = check(u);
        
        if(isCorrect) {
            return u+correct(v);
        }
        else {
            String result = "(" +correct(v)+ ")";
            u = u.substring(1, u.length()-1);
            return result+reverse(u);
        }
    }
    public String solution(String p) {
        return correct(p);
    }
}

2.説明

この関数は再帰的な問題です.そのため、主流を見つけることが最も重要です.
流れが見つからないとねじれて無限ループに陥るので注意!
しかし、この問題はすでに実施過程があり、その通りにすればよい.このプールの主なプロセスは次のとおりです.

Nullチェック

u,v文字列分割

v文字列null check

uがバランス文字列か

if-else、適用再帰

かっこ方向変更

まずは2からよく知っておきましょう

u、v文字列を分割する

// 균형 문자열 나누기
static String[] balance(String q) {
    String result[] = new String[2];
    int left = 0;
    int right = 0;
    for(int i=0; i<q.length(); i++) {
        if(q.charAt(i)=='(') {
            left++;
        }
        else {
            right++;
        }
        if(left==right) {
            result[0] = q.substring(0, left+right);
            result[1] = q.substring(left+right, q.length());
            break;
        }
    }
    return result;
}

この過程は簡単だ.
u,vで区切る場合、uは最小単位のバランス文字列でなければならないため、定義に従って、(和)の個数と同時に文字列をサブ文字列からサブ文字列に切り取る.

v文字列nullチェック

この方法は再帰的な方法である.
したがって、前の文字列分割プロセスは続行され、文字列は徐々に小さくなります.
これ以上割ってnull値を返さないとしたら?
もちろん間違います!
問題は、v文字列は空の値を許可しますが、u文字列はできません.
したがって、正しい文字列チェックメソッドのu文字列を受信しnullエラーを発行する前に、チェックを行ってください.

// check 메서드가 확인하기 전에 null 처리
if(u==null) {
   return "";
}

// u 문자열이 올바른 문자열인지 확인
boolean isCorrect = check(u);

uがバランス文字列であるかどうかを確認する

この部分は時間がかかりましたが、意外に解決策が簡単でした.
正しい文字列はペアの文字列です.
では、確認の方法は、もう半分を外してください.

// 반복
static String replay(String u, int count, int repeat) {
    // 짝을 제거
    String s = u.replace("()", "");
    count++;
    if(count==repeat) {
        return s;
    }
    return replay(s, count, repeat);
}
    
// 올바른 문자열인지 체크
static boolean check(String u) {
    int count = 0;
    int repeat = u.length()/2;
    String s = replay(u, count, repeat);
    
    return s.equals("") ? true : false;
}

ペアリングは「()」の形で現れます.
したがって、replaceを使用して「()」をすべて削除します.

// 짝을 제거
String s = u.replace("()", "");

しかし、それを回し続けると、無限の循環に陥ります.
したがって、最大繰返し回数repeatを「長さ/2」と指定します.
文字ごとに()を2文字ずつ置換するので、すべて置換しても長さ/2の文字しか置換できません.

// 반복
static String replay(String u, int count, int repeat) {
    // 짝을 제거
    String s = u.replace("()", "");
    count++;
    
    // 최대 반복수에 도달하면 반환
    if(count==repeat) {
        return s;
    }
    return replay(s, count, repeat);
}
    
// 올바른 문자열인지 체크
static boolean check(String u) {
    int count = 0;
    // 최대 반복수 제공
    int repeat = u.length()/2;
    String s = replay(u, count, repeat);
    
    return s.equals("") ? true : false;
}

したがって、check()に最大繰返し数を与え、replay()に再帰を返し、countを処理して最大繰返し数に達したときに再帰を終了する.

if-elseに再帰的に適用

正直、この部分は「この部分は鬼に当てはまるんじゃないかな~」と問題上明言していたのでスキップしました.

// 올바른 문자열 이라면
if(isCorrect) {
    return u+correct(v);
}

//아니라면
else {
    String result = "(" +correct(v)+ ")";
    u = u.substring(1, u.length()-1);
    return result+reverse(u);
}

かっこの方向を変更

も省略.els-ifゲートで方向を変えればいいです.

// 괄호 방향 바꾸기
static String reverse(String u) {
    StringBuilder result = new StringBuilder();
    for(int i=0; i<u.length(); i++) {
        // (를 )로
        if(u.charAt(i)=='(') {
            result.append(')');
        }
        
        // )를 (로
        else if(u.charAt(i)==')') {
            result.append('(');
        }
    }

3.結論

再帰については「元は自己繰返しの関数だったのか」としか知らず、無限ループやnullエラーが何度も発生し、多くのことを知りました.
いつ使うのか、無限ループに陥らないためには、まず何を考えているのかなどいろいろな面がわかってきました.
しかし、完全に私のものではないような気がします.
回帰問題については、他のサイトでもう少し説明する必要があるかもしれません.