[프로그래머스/Level2] 괄호 변환 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• 구현, 재귀

 

문제에서 말한 순서대로 구현하면 된다..

 

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 

→ int형 변수 open의 값을 통해 분리한다. 여는 괄호를 만나면 갯수+1, 닫는 괄호를 만나면 갯수 -1한다. 이 때 여는 괄호 수 = 닫는 괄호 수인 경우, "균형잡힌 괄호 문자열"이므로 현재 문자열을 u(균형잡힌 괄호 문자열)와 그 외 나머지 문자열 v로 분리한다.

StringBuilder u = new StringBuilder();
StringBuilder v = new StringBuilder();

int open = 0;   // '(' 개수

for(int i = 0 ; i < w.length() ; i++) {
    if(w.charAt(i) == '(') open++;
    else open--;

    if(open == 0) { // 균형잡힌 괄호 문자열인 경우, u와 v로 분리
        u.append(w.substring(0, i + 1));	// 균형잡힌 괄호 문자열
        v.append(w.substring(i + 1));		// 그 외 나머지 문자열
    }
}

3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
  3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 

if(check(u.toString())) {   // u가 올바른 괄호 문자열이라면
    u.append(solve(v.toString()));
}

 

→ 올바른 괄호 문자열인지 판단하는 메서드

private static boolean check(String s) {
    int cnt = 0;

    for(char c : s.toCharArray()) {
        if(c == '(') {
            cnt++;
        }
        else {
            cnt--;

            if(cnt < 0) return false;
        }
    }

    return true;
}

 

4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
  4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
  4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
  4-3. ')'를 다시 붙입니다. 
  4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
  4-5. 생성된 문자열을 반환합니다.

else {
    StringBuilder tmp = new StringBuilder();
    tmp.append("(");			// 4-1
    tmp.append(solve(v.toString()));    // 4-2) v에 대해 재귀호출 수행한 후 붙이기
    tmp.append(")");			// 4-3
    tmp.append(reverse(u.toString()));  // 4-4) u 조작해 붙이기

    return tmp.toString();  	// 4-5) 생성된 새 문자열 반환                    
}

 

→ 4-4단계 수행하는 메서드

private static String reverse(String str) {
    StringBuilder s = new StringBuilder();

    // 첫 번째랑 마지막 두 문자 제외하고 뒤집기
    for(int i = 1 ; i < str.length() - 1 ; i++) {
        s.append(str.charAt(i) == '(' ? ')' : '(');
    }

    return s.toString();
}

 

 

🔺 코드

import java.util.*;
 
class Solution {
    public String solution(String p) {                
        if(check(p))
            return p;
        return solve(p);
    }
    
    // 균형잡힌 괄호 문자열 -> 올바른 괄호 문자열 변환ㅁ ㅔ서드
    private static String solve(String w) {
        StringBuilder u = new StringBuilder();
        StringBuilder v = new StringBuilder();
 
        if(w.length() == 0)   return "";
        
        int open = 0;   // '(' 개수
        
        for(int i = 0 ; i < w.length() ; i++) {
            if(w.charAt(i) == '(') open++;
            else open--;
            
            if(open == 0) { // 균형잡힌 괄호 문자열인 경우
                u.append(w.substring(0, i + 1));
                v.append(w.substring(i + 1));
                
                if(check(u.toString())) {   // u가 올바른 괄호 문자열이라면
                    u.append(solve(v.toString()));
                }
                else {
                    StringBuilder tmp = new StringBuilder();
                    tmp.append("(");
                    tmp.append(solve(v.toString()));    // v에 대해 재귀호출 후 붙이기
                    tmp.append(")");
                    tmp.append(reverse(u.toString()));  // u 조작해 붙이기
 
                    return tmp.toString();  // 새 문자열 반환                    
                }
                
                break;
            }
        }
        
        return u.toString();    // u가 올바른 괄호 문자열인 경우에만 도달
    }
 
    // 올바른 괄호 문자열 판단 메서드
    private static boolean check(String s) {
        int cnt = 0;
        
        for(char c : s.toCharArray()) {
            if(c == '(') {
                cnt++;
            }
            else {
                cnt--;
 
                if(cnt < 0) return false;
            }
        }
        
        return true;
    }
    
    // 변환하는 메서드
    private static String reverse(String str) {
        StringBuilder s = new StringBuilder();
        
        // 앞뒤 두 문자 제외하고 변환
        for(int i = 1 ; i < str.length() - 1 ; i++) {
            s.append(str.charAt(i) == '(' ? ')' : '(');
        }
        
        return s.toString();
    }
}

 

 

---

💦 어려웠던 점

- 그냥 문제에서 말한 순서대로 그대로 구현하면 되는데 이걸 못 했다..... 구현력을 더 키워야 한다...ㅠ

- u가 앞쪽에 있는 경우, 뒤쪽에 있는 경우 이렇게 나눠서 진행하려고 했었는데 그게 아니고 그냥 문제에서 말한 그대로 구현하면 되는 것이었다,,,^^

 

 

🧐 새로 알게 된 내용

- 균형잡힌 괄호 문자열인지 확인할 때 스택을 써야하나 라는 생각을 했는데 그냥 변수 하나로만 더했다가 뺐다가 하면 더 간단하게 해결되는 문제였다,,

- 메서드 분리 안 해서 한꺼번에 작성하려 했더니 더 복잡하게 생각된 것 같다... 다음에는 로직에 맞는 메서드명 순서대로 적어놓고 그 다음에 필요한 메서드 구현하는 것으로!!

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이 참고

[프로그래머스,Level 2] 괄호 변환 (JAVA 구현)