[프로그래머스] Lv.2 괄호 변환

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

프로그래머스

 

문제 설명

'('와 ')'로만 이루어진 문자열이 있을 경우, '('의 갯수와 ')'의 개수가 같다면 이를 <균형 잡힌 괄호 문자열>이라고 부른다.

그리고 여기에 '('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이를 <올바른 괄호 문자열>이라고 부른다.

예를 들어, "(()))(" 와 같은 문자열은 <균형 잡힌 괄호 문자열>이지만 <올바른 괄호 문자열>은 아닙니다.

반면에 "(())()" 은 <균형 잡힌 괄호 문자열>이면서 동시에 <올바른 괄호 문자열>입니다.

 

'('와 ')'로만 이루어진 문자열 w가 <균형 잡힌 괄호 문자열>이라면 다음과 같은 과정을 통해 <올바른 괄호 문자열>로 변환할 수 있습니다.

 

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환한다.

2. 문자열 2를 두 <균형잡힌 괄호 문자열> u, v로 분리한다. 단, u는 <균형잡힌 괄호 문자열>로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있다.

3. 문자열 u가 <올바른 괄호 문자열>이라면 문자열 v에 대해 1단계부터 다시 수행한다.

    3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환한다.

4. 문자열 u가 <올바른 괄호 문자열>이 아니라면 아래 과정을 수행한다.

    4-1. 빈 문자열에 첫 번째 문자로 '('를 붙인다.

    4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙인다.

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

    4-4. 생성된 문자열을 반환한다.

<균형잡힌 괄호 문자열> p가 주어질 때, 주어진 알고리즘을 수행해 <올바른 괄호 문자열>로 변환한 결과를 return 하는 solution 함수를 완성해 주세요.

---

📗 풀이과정

해당 문제는 정말로 주어진 알고리즘을 그대로 구현하기만 하면 됩니다.

 

전체코드

import java.util.*;
class Solution {
    public String solution(String p) {
        String answer = "";
        
        answer = makeCorrectString(p);
        
        
        return answer;
    }
    String makeCorrectString(String w){
        
        //빈 문자열이 들어온다면 그대로 반환
        if(w.length()==0) return w;
        
        //w를 "균형잡힌 괄호 문자열" u,v로 분리
        int idx,open,close;
        idx=open=close=0;
        for(int i=0;i<w.length();i++){
            if(w.charAt(i)=='(') open++;
            else close++;
            
            if(open==close){ idx=i;break;}
        }
        String u = w.substring(0,idx+1);
        String v = w.substring(idx+1,w.length());
        
        //System.out.println(u+" "+v);
        
        //u가 올바른 문자열이면
        if(isCorrect(u)) return u+makeCorrectString(v);
        
        //u가 올바른 문자열이 아니라면
        String temp="(";
        temp+=makeCorrectString(v);
        temp+=")";
        u=u.substring(1,u.length()-1);
        for(int i=0;i<u.length();i++){
            if(u.charAt(i)=='(') temp+=')';
            else temp+='(';
        }
        return temp;
    }
    boolean isCorrect(String u){
        Stack<Character> stack = new Stack<>();
        
        for(int i=0;i<u.length();i++){
            if(u.charAt(i)=='(') stack.push('(');
            else{
                if(stack.isEmpty()){ stack.push(')'); break;}//비어있는데 꺼내려고 할 때
                else stack.pop();
            }
        }
        if(stack.isEmpty()) return true;
        else return false;
    }
}