[프로그래머스_Lv.2] 괄호 변환 (DFS_Java)

DFS에 조금 자신감이 붙어서

프로그래머스에 있는 문제에 도전했다가

호되게 당했다.

 

기본기부터 탄탄히 다지는 걸로..!

근데 변명하자면 이건 코드 작성이 어려운 것이 아니라,

문제 이해가 어려운 것이다.

 

---

문제

 

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

프로그래머스

 

 

---

설계

 

알고리즘 설계 [접근 방법] : DFS

이 문제는 나와있는 조건대로 문제를 풀면 된다. 주어진 조건대로 코드를 작성하면서 비교하는 것이 중요한 것같다.

문제 설명이 다소 복잡하게 나와있다고 생각해서, 문제를 정확하게 이해하고 푸는 것도 중요한 것 같다.

 

여기서 '균형잡인 괄호 문자열'은 문자열에서 '('와 ')'의 개수가 같은 것이다. '올바른 괄호 문자열'은 균형잡힌 괄호 문자열에서 괄호의 짝이 맞는 경우다. 만약 '(()))('와 같은 경우는 균형잡힌 괄호 문자열에 속하지만, 올바른 괄호 문자열은 아니다.

 

DFS를 구현하여 재귀로 풀어야하는 문제다. 다만 DFS를 통해 재귀를 하는 과정에서 값을 새롭게 바꾸어 주어야하는 부분(4번)이 있는데, 이곳에서 실수만 하지 않는다면 괜찮을 듯 싶다.

 

풀이 과정

1.

올바른 문자열인지 확인하는 메서드를 만든다.

stack을 활용하여 '('라면 stack에 넣어주고, ')'라면 stack에서 괄호를 제거한다. 괄호를 제거하려고 할 때, stack이 비어있다면 '('가 부족한 것이므로 올바른 문자열이 아니다. 그러므로 false를 반환하면 된다.

그리고 문자열 탐색을 끝나고 stack의 사이즈가 0이 아니라면 '('의 개수가 ')'보다 많았던 것이므로, 역시 false를 반환하면 된다.

이게 아니라면 올바른 괄호 문자열이므로 true를 반환한다.

 

2.

DFS 메서드를 생성하고, 1번 조건인 빈 문자열일 경우에는 그냥 빈 문자열을 반환한다.

 

3.

2번 조건인 str문자열을 균형잡힌 문자열인 u, v로 나눠야 한다.

str문자열을 반복문을 돌면서 현재 문자가 '('라면, cnt1 변수를 +1해주고, ')'라면 cnt2 변수를 +1해준다. 그리고 이때 cnt1과 cnt2의 개수가 같다면 균형잡힌 괄호 문자열이므로 여기서 u와 v로 잘라준다.

 

4.

u가 올바른 괄호 문자열인지 확인하고, 맞다면 v에 대해 DFS를 실행한다.

그리고 그 값을 u뒤에 더해준다.

 

5.

u가 올바른 괄호 문자열이 아니라면, 새로운 문자열 result를 생성한다.

result에는 처음에 '('를 붙이고,  그 후 DFS(v)를 실행한 값, 마지막에 괄호 ')'를 저장한다.

그리고 문자열 u에 대해 처음과 마지막을 제외하고, 문자열 반전을 시켜 result에 더해준다. 여기서 처음과 끝을 제외하고 반전시킬 때, subString을 사용하게 되면 문자열 길이가 1이나 2일 때 에러가 발생하게 된다.

그러므로 반복문 조건을 1부터 u.length()-2까지로 설정하는 것이 맞다.

모든 조건이 완성되면 result를 반환한다.

 

7.

처음 입력받은 문자열 p를 DFS에 실행시킨다.

 

 

---

코드

 

import java.util.*;

class Solution {
    public String solution(String p) {
        String answer = DFS(p);
        return answer;
    }
    
    //올바른 문자열인지 확인
    public static boolean check(String str){
        Stack<Character> stack = new Stack();
        
        for(int i=0; i<str.length(); i++){
            if(str.charAt(i)=='(') stack.add('(');
            else if(str.charAt(i)==')' && stack.isEmpty()) return false;
            else if(str.charAt(i)==')' && !stack.isEmpty()) stack.pop();   
        }
        
        if(!stack.isEmpty()) return false;
        else return true;
    }
    
    //문자열 변경
    public static String DFS(String str) {
        
        //1. 입력이 빈 문자열인 경우, 빈 문자열을 반환
        if(str.length()==0) return str;
    
        //2. 균형잡힌 괄호 문자열" u, v로 분리
        String u = "";
        String v = "";
        
        int cnt1 = 0;
        int cnt2 = 0;
        
        for(int i=0; i<str.length(); i++){
            if(str.charAt(i)=='(') cnt1++;
            else cnt2++;
            
            if(cnt1==cnt2) {
                u = str.substring(0, i+1);
                if(i<str.length()-1) v = str.substring(i+1, str.length());
                break;
            }
        }
    
        //3. u가 "올바른 괄호 문자열" 이라면, v에 대해 1단계부터 다시 수행
        if(check(u)) return u+DFS(v);
        
        //4. u가 "올바른 괄호 문자열"이 아니라면
        else {
            
            String result = "(" + DFS(v) + ")";       //4-1부터 4-3
            
            for(int i=1; i<u.length()-1; i++){         //4-4 u를 자르고 result에 붙이기
                if(u.charAt(i)=='(') result+=")";
                else result+="(";
            }
            
            return result;
        }
    }
}

 

 

 

(❁´◡`❁)

끝!