[프로그래머스][Level2][Java] 괄호 변환

문제

문제가 길어서 따로 문제 링크를 첨부

https://programmers.co.kr/learn/courses/30/lessons/60058

코딩테스트 연습 - 괄호 변환

문제의 핵심

풀이 코드

풀이 코드가 길어서 부분부분으로 나눠서 설명 후 전체코드를 올리겠다.

우선, 이 문제를 난 4개의 메서드로 나누었다.

1. 올바른 괄호인지 판단하는 메서드

2. 올바른 괄호가 아닐때, 올바른 괄호로 바꿔주는 메서드

3. 문제의 4-4단계를 실행하는 메서드

4. 1,2,3단계를 통합해서 실행할 solution 메서드

위와 같이 메서드를 나눈 이유는 문제를 풀때, 재귀를 사용해야 되는 경우도 있어서 나눠서 푸는 것이 좋을 것 같아서이다.

 

1. 올바른 괄호인지 판단하는 메서드

public static boolean check(String s) {  //올바른 괄호 판단
    int cnt = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {         // (일경우 cnt+1
            cnt++;
        } else {                          // )일경우 cnt-1
            cnt--;
            if (cnt < 0) {                  // )를 만나서 cnt-1했을 때, cnt가 0보다 작으면 )가 더 많다는 뜻이므로 false return
                return false;
            }
        }
    }                                   // 위의 케이스를 다 통과한 경우 true return
    return true;
}

설명은 주석에 있으므로 자세한 설명은 생략

 

2. 올바른 괄호가 아닐때, 올바른 괄호로 바꿔주는 메서드

public static String split(String tmp) { //u,v로 나눈 뒤, 다시 합침
    int cnt = 0;
    String u = "";
    String v = "";
    if (tmp.length() == 0) {            //빈 문자열일 때, 빈 문자열 return
        return "";
    }
    for (int i = 0; i < tmp.length(); i++) {
        if (tmp.charAt(i) == '(') {     // check메서드와 마찬가지로 (일때 +, )일때 -를 cnt에 해줌
            cnt++;
        } else {
            cnt--;
        }
        if (cnt == 0) {                 // cnt가 0이란 말은 처음부터 i번째까지가 균형잡힌 문자열이란 말임
            u = tmp.substring(0, i + 1);    // 그때 u에 균형잡힌 문자열을 넣고
            v = tmp.substring(i + 1);       // 나머지를 v에 넣는다.
            if (check(u)) {          // u가 균형잡힌 문자열이고 올바른 문자열 일때,
                u = u + split(v);    // u에 v를 재귀시켜서 다시 넣어준다.(3단계 실행)
            }else{                  // u가 균형잡힌 문자열이지만 올바른 문자열이 아닐 때,
                String emp = "";
                emp = "(" + emp + split(v) + ")" + reverse(u);  // 4단계를 그대로 실행
                return emp;
            }
            //블로그에 자세한 설명 기재 - 1
            break;
        }
    }
    return u;
}

여기서 다른 것은 설명을 해놓았지만 break를 걸어둔 이유에 대해서 설명을 하자면

위의 코드에서 균형잡힌 문자열을 u에 넣고 나머지를 v에 넣고 재귀를 사용해서 균형잡힌 문자열을 다시 split함수에 넣어서 푼다. 즉, 균형잡힌 문자열을 한 번 구하고 나머지는 재귀로 푸는 형식인데 break를 걸어주지 않으면 균형잡힌 문자열을 한 번 구하고 반복문에 의해서 또 그다음 균형잡힌 문자열을 또 구해서 또 재귀를 돌리기 때문에 원래 구하려던 문자열에서 이상하게 더 괄호가 늘어나기 때문에 꼭 break를 한번 걸어줘야 한다.

 

3. 문제의 4-4단계를 실행하는 메서드

public static String reverse(String s) { //u 변환
    String tmp = "";
    if(s.length()==0){  //빈 문자열일 경우, 빈 문자열 반환
        return "";
    }else {             // u의 제일 처음과 끝을 제거한 후, ( -> )로, ) -> (로 바꿔준다.
        s = s.substring(1, s.length() - 1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                tmp += ")";
            }else{
                tmp += "(";
            }
        }
        return tmp;
    }
}

여기서 좀 실수한 것이 문제를 잘못이해해서

u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.

이 말이 u의 앞뒤를 뒤집는 즉, "())()(" 이것이면 앞뒤를 뒤집어서 "()())("이렇게 바꾸라는 말인줄 알고 StringBuilder.reverse를 사용해서 뒤집었는데 알고보니

) -> (이렇게 바꾸고 ) -> ( 이렇게 뒤집으란 소리였다...

즉, "())()(" 이것이면 ")(()()"이렇게 바꾸라는 소리였다...그것도 모르고 한참을 헤맸다...

 

4. 1,2,3단계를 통합해서 실행할 solution 메서드

public String solution(String p) {  //답
    String answer = "";
    if(check(p)){                   //올바룬 문자열일 경우, 그대로 반환
        return p;
    }else{                          //올바른 문자열이 아닌 경우
        answer = split(p);          //split을 통해 문자열을 교정해준다.
    }
    return answer;
}

 

1,2,3,4를 다 합친 전체 코드

public static boolean check(String s) {  //올바른 괄호 판단
    int cnt = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {         // (일경우 cnt+1
            cnt++;
        } else {                          // )일경우 cnt-1
            cnt--;
            if (cnt < 0) {                  // )를 만나서 cnt-1했을 때, cnt가 0보다 작으면 )가 더 많다는 뜻이므로 false return
                return false;
            }
        }
    }                                   // 위의 케이스를 다 통과한 경우 true return
    return true;
}

public static String split(String tmp) { //u,v로 나눈 뒤, 다시 합침
    int cnt = 0;
    String u = "";
    String v = "";
    if (tmp.length() == 0) {            //빈 문자열일 때, 빈 문자열 return
        return "";
    }
    for (int i = 0; i < tmp.length(); i++) {
        if (tmp.charAt(i) == '(') {     // check메서드와 마찬가지로 (일때 +, )일때 -를 cnt에 해줌
            cnt++;
        } else {
            cnt--;
        }
        if (cnt == 0) {                 // cnt가 0이란 말은 처음부터 i번째까지가 균형잡힌 문자열이란 말임
            u = tmp.substring(0, i + 1);    // 그때 u에 균형잡힌 문자열을 넣고
            v = tmp.substring(i + 1);       // 나머지를 v에 넣는다.
            if (check(u)) {          // u가 균형잡힌 문자열이고 올바른 문자열 일때,
                u = u + split(v);    // u에 v를 재귀시켜서 다시 넣어준다.(3단계 실행)
            }else{                  // u가 균형잡힌 문자열이지만 올바른 문자열이 아닐 때,
                String emp = "";
                emp = "(" + emp + split(v) + ")" + reverse(u);  // 4단계를 그대로 실행
                return emp;
            }
            //블로그에 자세한 설명 기재 - 1
            break;
        }
    }
    return u;
}

public static String reverse(String s) { //u 변환
    String tmp = "";
    if(s.length()==0){  //빈 문자열일 경우, 빈 문자열 반환
        return "";
    }else {             // u의 제일 처음과 끝을 제거한 후, ( -> )로, ) -> (로 바꿔준다.
        s = s.substring(1, s.length() - 1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                tmp += ")";
            }else{
                tmp += "(";
            }
        }
        return tmp;
    }
}


public String solution(String p) {  //답
    String answer = "";
    if(check(p)){                   //올바룬 문자열일 경우, 그대로 반환
        return p;
    }else{                          //올바른 문자열이 아닌 경우
        answer = split(p);          //split을 통해 문자열을 교정해준다.
    }
    return answer;
}

public static void main(String[] args) {    //테스트 케이스
    Solution31 test = new Solution31();
    String s = "()))((()";
    System.out.println(test.solution(s));
}