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

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

프로그래머스

 

문제 풀이

해당 문제는 알고리즘을 제시를 해주고 구현만 하면 되는 문제이다. 직접 설계까지 하는 문제였다면 level2보다 훨씬 높았을 거라고 생각한다. 알고리즘을 제시해줬으니 딱히 풀이할 문제도 없다. 각자 언어에 맞게 문법만 알면 반 이상은 구현할 수 있을 것이다.

다음으로 필요한 기술은 3번 지문에서 알 수 있듯이

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

1단계부터 다시 수행한다 -> 재귀 라는 것을 떠올려야 한다.

다음 힌트는 u, v로 분리되는데 u는 균형잡힌 괄호 문자열로 더 이상 분리할 수 없다. 이 부분이 포인트다

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

즉, 앞에서부터 가장 작은 단위의 균형잡힌 괄호 문자열을 분리해라.

힌트는 여기까지다.

이렇게 분리한 서브스트링 u,v를 가지로 해당 알고리즘에 맞게 순서대로 진행해보자.

1. 우선 최소 단위의 균형 잡힌 문자열의 마지막인덱스를 반환하는 함수를 구현하여 해당 인덱스를 통해 서브스트링을 분리
2. 올바른 괄호 문자열인지 반환

하는 함수를 만들어두고 구현하였다. 나머지는 주석을 통해 쉽게 따라갈 수 있을 것이다.

코드

class Solution {

    // "균형잡힌 괄호 문자열"의 인덱스 반환
    public int balancedIndex(String p) {
        int count = 0; // 왼쪽 괄호의 개수
        for (int i = 0; i < p.length(); i++) {
            if (p.charAt(i) == '(') count += 1;
            else count -= 1;
            if (count == 0) return i;
        }
        return -1;
    }

    // "올바른 괄호 문자열"인지 판단
    public boolean checkProper(String p) {
        int count = 0; // 왼쪽 괄호의 개수
        for (int i = 0; i < p.length(); i++) {
            if (p.charAt(i) == '(') count += 1;
            else {
                if (count == 0) { // 쌍이 맞지 않는 경우에 false 반환
                    return false;
                }
                count -= 1;
            }
        }
        return true; // 쌍이 맞는 경우에 true 반환
    }

    public String solution(String p) {
        String answer = "";
        if (p.equals("")) return answer;
        int index = balancedIndex(p);
        String u = p.substring(0, index + 1);
        String v = p.substring(index + 1);
        // "올바른 괄호 문자열"이면, v에 대해 함수를 수행한 결과를 붙여 반환
        if (checkProper(u)) {
            answer = u + solution(v);
        }
        // "올바른 괄호 문자열"이 아니라면 아래의 과정을 수행
        else {
            answer = "(";
            answer += solution(v);
            answer += ")";
            u = u.substring(1, u.length() - 1); // 첫 번째와 마지막 문자를 제거
            String temp = "";
            for (int i = 0; i < u.length(); i++) {
                if (u.charAt(i) == '(') temp += ")";
                else temp += "(";
            }
            answer += temp;
        }
        return answer;
    }
}

느낀점

알고리즘을 알려줘도 생각보다 이해하는데 오래걸렸고 코딩을 하는데에도 시간을 많이 허비했다. 알고리즘은 직접 설계해야 편한데 남이 짜준 방법대로 구현하려니 더 힘들게 느껴졌다. 하지만 어려운 문제의 알고리즘을 설계하는 것은 더 어렵다. 그냥 다 어렵다.