LV2 괄호 변환 (Java)

 

---

 

문제

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

프로그래머스

 

풀이

 

사실 이 문제는 하라는대로 구현만 하면 슉슉 풀리는 문제이다. 단 지문이.. 이해하기 조금 난해하다는게 문제다. 슈도 코드를 작성하면 조금 더 쉽지 않을까 생각한다.

 

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 
   단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, 
   v는 빈 문자열이 될 수 있습니다. 
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
  3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
  4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
  4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
  4-3. ')'를 다시 붙입니다. 
  4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
  4-5. 생성된 문자열을 반환합니다.
  
  
answer = mySolution(문자열)
  
func mySolution(문자열)
  
  if 문자열 == "":
    return ""
  u = 균형잡힌 문자열 만드는 함수(문자열)
  v = 문자열에서 u를 제외한 부분
  
  if 올바른 문자열 검사 함수(u)
    return u + mySolution(v)
  
  // 아닐경우에는 아래 수행
  
  새문자열 = ""
  새문자열 += "("
  새문자열 += mySolution(v)
  새문자열 += ")"
  
  for(i=1; i<u.length()-1; i++)
    if u[i] =='(': 새문자열 += ")"
    else 새문자열 += "("
  
  return 새문자열

 

위처럼 작성해두면 코드는 정말 쉽게 작성할 수 있다. 균형맞는 문자열인지는 괄호 개수만 체크하면 되고, 올바른  문자열인지는 정통적으로 괄호의 짝을 검사하는 스택방식을 활용하면 된다.

 

만약 올바른 문자열이 아니라면 그때는 새문자열에 대한 로직을 수행하면 된다.

 

 

코드

import java.util.*;

class Solution {

    // 균형 잡힌 문자열 반환
    public String getBalanced(String s){
        int left = 0;
        int right = 0;
        int idx = 0;
        for(int i=0; i<s.length(); i++, idx++){
            if(left == right && left != 0) break;
            if(s.charAt(i) == '(') left++;
            else right++;
        }
        return s.substring(0, idx);
    }

    // 올바른지 검사
    public Boolean valid(String s){
        Stack<Character> st = new Stack<>();
        for(int i=0; i<s.length(); i++){
            char ch = s.charAt(i);
            if(st.empty()){
                st.push(ch);
            } else{
                if(st.peek() == '(' && ch == ')'){
                    st.pop();
                } else{
                    st.push(ch);
                }
            }
        }
        return st.empty();
    }

    public String makeU(String s){

        // 1. 빈 문자열이면
        if(s.equals("")){
            return s;
        }

        // 2. u, v로 변환
        String u = this.getBalanced(s);
        String v = "";
        if(u.length() < s.length()){
            v = s.substring(u.length());
        }
        // 3. u가 올바른지 확인
        if(this.valid(u)) {
            return u + makeU(v);
        }

        // 4. 올바르지 않다면 로직 수행
        StringBuilder temp = new StringBuilder("(");
        temp.append(makeU(v));
        temp.append(")");
        for(int i=1; i<u.length()-1; i++){
            if(u.charAt(i) == '('){
                temp.append(")");
            } else{
                temp.append("(");
            }
        }
        return temp.toString();
    }

    public String solution(String p) {
        return this.makeU(p);
    }
}

 

후기

 

예전에 파이썬으로 풀고 자바로 다시 풀었는데, 이해만 하면 쉬운문제다. 근데 지문이 좀 헷갈리긴한다..