괄호 변환

유태형·2022년 3월 10일

프로그래머스 - Level 2

목록 보기

29/36

문제

문제 분석

특이하게도 알고리즘을 문제에서 제시하였습니다. 어려워서라기 보단 모호해질수 있어서 그런것 같네요.
균형잡힌 괄호 문자열과 올바른 괄호 문자열이 무엇을 뜻하는지와 문제에서 설명하는 변환방식이 어떤 건지 정확히 짚고 가야 다른 길로 빠지는걸 방지할 수 있을것 같습니다.

풀이

임의로 정해놓은 것이 많은 문제여서 의미하는 바가 무엇인지 정확히 짚고 가는것이 중요한 문제인것 같습니다.

균형잡힌 괄호 문자열 : 문자열 내에(와 )의 수가 동일
올바른 괄호 문자열 : 문자열 내에 (와 )의 수 뿐만 아니라 순서도 다 맞춤
u : 최소크기의 균형잡힌 괄호 문자열
v : 문자열에서 u를 제외한 뒷 부분
p : 매개변수로 균형잡힌 괄호 문자열

여기서 주의해야 할 것이 두가지 있습니다.

첫번째로 올바른 괄호 문자열이 균형잡힌 괄호 문자열의 부분집합 인 점입니다. 균형잡힌 괄호 문자열에서 괄호의 순서를 맞추면 올바른 괄호 문자열이 됩니다.

두번째는 균형잡힌 문자열에서 균형잡힌 문자열을 빼면 균형잡힌 문자열입니다. 흔히 짝수 - 짝수 = 짝수듯이 같은 수의 (, )쌍이 나가면 (, )쌍이 유지됩니다.

u와 v

		int bal = BALANCE;
        String v = "";
        int index;

        if (u.equals(""))
            return u;

        //균형잡힙 괄호 문자열 찾기, u찾기
        for(index = 0;index<u.length();index++){
            char c = u.charAt(index);

            //문자'('는 +1, ')'는 -1, 양수면 '('가 많고, 음수면 ')'가 많음
            switch(c){
                case '(':
                    bal++;
                    break;
                case ')':
                    bal--;
                    break;
            }

            if(bal == BALANCE) //+1과 -1갯수 즉 '('와 ')'갯수가 동일
                break;
        }

        v = u.substring(index+1); //뒷 문자열
        u = u.substring(0,index+1); //균형 문자열

u는 최소 크기의 균형잡힌 괄호 문자열이므로 (와 )의 수가 같은면 반환하는데 이때 (는 +1, )는 -1을 함으로써 0일때 (, )의 수가 같을때 입니다.

괄호 반환

		 //'('로 시작하면 올바른, ')'로 시작하면 균형, 문자열은 무조건 균형임을 응용
        if(u.charAt(0) == '(')
            return u + bracket(v); //3-1
        else{           

            u = u.substring(1,u.length()-1); //4-4  
            u = u.replaceAll("\\(","열");
            u = u.replaceAll("\\)","닫"); //바꾸기위한 치환                    
            u = u.replaceAll("열",")");
            u = u.replaceAll("닫","("); //( 와 )치환

            return "(" + bracket(v) + ")" + u; //4-1, 4-2, 4-3, 4-5
        }

u가 균형잡힌 괄호 문자열인가 올바른 괄호 문자열인가에 따라 반환하는 문자열이 달라집니다.

올바른 괄호 문자열 : u와 재귀적으로 구한 v를 합칩니다.
균형잡힌 괄호 문자열 : u의 첫, 마지막 괄호를 삭제하고 내부 괄호들은 서로 반대로 치환합니다.

코드

class Solution {
    public static final int BALANCE = 0; //0은 '(' 와 ')'의 수가 같음을 의미
    
    public String solution(String p) {
        String answer = "";
        answer = bracket(p);
        return answer;
    }
    
    //괄호 재귀적
    public static String bracket(String u){
        int bal = BALANCE;
        String v = "";
        int index;
        
        if (u.equals(""))
            return u;
        
        //균형잡힙 괄호 문자열 찾기, u찾기
        for(index = 0;index<u.length();index++){
        	char c = u.charAt(index);
        	
            //문자'('는 +1, ')'는 -1, 양수면 '('가 많고, 음수면 ')'가 많음
            switch(c){
                case '(':
                    bal++;
                    break;
                case ')':
                    bal--;
                    break;
            }
            
            if(bal == BALANCE) //+1과 -1갯수 즉 '('와 ')'갯수가 동일
                break;
        }
        
        v = u.substring(index+1); //뒷 문자열
        u = u.substring(0,index+1); //균형 문자열
        
        //'('로 시작하면 올바른, ')'로 시작하면 균형, 문자열은 무조건 균형임을 응용
        if(u.charAt(0) == '(')
            return u + bracket(v); //3-1
        else{        	
        	
        	u = u.substring(1,u.length()-1); //4-4 	
            u = u.replaceAll("\\(","열");
            u = u.replaceAll("\\)","닫"); //바꾸기위한 치환                    
            u = u.replaceAll("열",")");
            u = u.replaceAll("닫","("); //( 와 )치환
            
            return "(" + bracket(v) + ")" + u; //4-1, 4-2, 4-3, 4-5
        }
    }
}