(2020카카오) 괄호변환 Java

 

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

문제가 내용이 괴랄해서 아래의 영상설명을 참조했다

www.youtube.com/watch?v=Bc34h7xPTL8

 

 

어려운 문제중에서 이런식으로 코드 메뉴얼을 주는 경우, 그대로 따라 구현하기만하면 반은 성공할 수 있다고 본다.

 

그리고 프로그래머스에서 solution메소드를 직접 재귀로 돌리는 방법이 포함되어있으니 참고해보는게 좋겠다.

 

분할정복 문제에 해당한다.

 

분할정복법은 주어진 문제를 작은 사례로 나누고(Divide) 각각의 작은 문제들을 해결하여 정복 (Conquer)하는 방법이다. 분할정복법은 문제의 사례를 2개 이상의 더 작은 사례로 나눈다.

 

import java.util.*;

class Solution {
    int pos;

    boolean isCorrect(String str){
        boolean ret = true;

        int left =0, right = 0;//오른쪽 왼쪽 카운팅
        Stack<Character> mystack = new Stack<>();

        for(int i =0; i<str.length(); ++i){
            if(str.charAt(i) == '(' ){
                left++;
                mystack.push('(');
            }else{
                right++;
                if(mystack.isEmpty()){
                    ret=false;
                }else{
                    mystack.pop();
                }
            }
            if(left==right){//균형잡힌 괄호문자열인경우. (최초로)
                //u,v를 분리하는부분
                pos =i+1;//v의 시작위치이자, u의 length로 사용
                return ret;
            }
        }
        return true;//여기까지 올일은없음.
    }

    public String solution(String p) {
        if(p.isEmpty()) return p;

        boolean correct = isCorrect(p);
        String u = p.substring(0, pos);
        String v = p.substring(pos, p.length());

        if(correct){//3번인경우(올바른괄호문자열이라면)
            return u + solution(v);//재귀적으로 solution메소드 호출
        }
        //else
        //올바른문자열이 아니면.
        String answer = "(" + solution(v) + ")";
        for(int i=1; i<u.length()-1; i++){//4-4
            if(u.charAt(i) == '(')
                answer+=")";
            else
                answer+="(";
        }

        return answer;//4-5
    }
}