[이코테][Java] 괄호 변환

[문제링크]

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

---

문제 설명

개발자 "콘"은 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 한다.

균형잡힌 괄호 문자열 - '(' 개수와 ')'의 개수가 맞을 경우

올바른 괄호 문자열 - '('와 ')'의 괄호 짝도 모두 맞을 경우

ex) "(()))(" 는 균형잡힌 괄호 문자열이지만 올바른 괄호 문자열은 아니다.

       "(())()"는 균형잡힌 괄호 문자열이면서 올바른 괄호문자열이다.

 

'('와 ')'로만 이루어진 문자열 w가 "균형잡힌 괄호 문자열"이라면, 다음과 같은 과정을 거쳐서 "올바른 괄호 문자열"로 변환할 수 있다.

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
  3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
  4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
  4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
  4-3. ')'를 다시 붙입니다. 
  4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
  4-5. 생성된 문자열을 반환합니다.

 

"균형잡힌 괄호 문자열" p가 주어질 때, "올바른 괄호 문자열"로 변환한 결과를 리턴하는 함수를 완성하시오.

 

입력조건

• 균형잡힌 괄호 문자열 p
• p의 길이: 2 <= p <= 1000인 짝수
• p를 이루는 '('와 ')'의 개수는 항상 같고, p가 이미 올바른 괄호 문자열이라면 그대로 return

출력조건

• 문자열 p를 올바른 괄호 문자열

입출력 예시

입력예시	출력예시
"(()())()"	"(()())()"
")("	"()"
"()))((()"	"()(())()"

 

 

 

 

문제 풀이

• dfs 알고리즘 사용
• isBalance()
  - 균형잡힌 괄호 문자열인지 판별하는 함수
  - "("와 ")"의 개수가 같은 지점의 index를 구한다.
  - substring() 함수로 균형잡힌 괄호 문자열 u, v로 분리한다.
• isCorrect()
  - 올바른 괄호 문자열인지 판별하는 함수
  - 문제에서는 균형잡힌 괄호 문자열 u가 올바른 괄호 문자열인지 아닌지 판별하면 된다.
  - stack을 사용해서 "("일 경우 push, ")"일 경우 pop
  - pop을 할 때, stack이 비어있으면 해당 문자열은 올바른 괄호 문자열이 아니다.
• reverse()
  - 4-4 단계를 수행하는 함수
  - substring() 함수로 첫 번째와 마지막 문자를 제거
  - replace() 함수로 남은 나머지 문자열의 괄호 방향을 뒤집는다. → "("는 ")"으로, ")"는 "("으로

import java.util.*;

class Solution {
    private static String u = "", v = "";

    public String solution(String p) {
        //1. 빈 문자열일 경우, 빈 문자열 그대로 반환
        if (p.isEmpty()) {
            return p;
        }

        //2. 문자열 w를 균형잡힌 괄호 문자열 u, v로 분리
        isBalance(p);

        //u가 "올바른 괄호 문자열"인지 아닌지 확인
        if (isCorrect(u)) {     //3. u가 "올바른 괄호 문자열"일 경우
            return u + solution(v);
        } else {    //4. u가 "올바른 괄호 문자열"이 아닐 경우
            String re = reverse(u);
            return "(" + solution(v) + ")" + re;
        }
    }

    //균형잡힌 괄호 문자열 확인
    private static void isBalance(String p) {
        int left = 0, right = 0;

        for (int i = 0; i < p.length(); i++) {
            if (p.charAt(i) == '(') {   //"("
                left++;
            } else {                    //")"
                right++;
            }

            if (left == right) {
                u = p.substring(0, i + 1);
                v = p.substring(i + 1);
                break;
            }
        }
    }

    //올바른 괄호 문자열 확인
    private static boolean isCorrect(String u) {
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < u.length(); i++) {
            if (u.charAt(i) == '(') {
                stack.push(u.charAt(i));
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                stack.pop();
            }
        }
        return true;
    }

    //u의 나머지 괄호 방향 뒤집기
    private static String reverse(String u) {
        u = u.substring(1, u.length()-1);
        u = u.replace('(', '.');
        u = u.replace(')', '(');
        u = u.replace('.', ')');
        return u;
    }

}

 

 

문제를 이해하는데 시간이 오래걸렸지만, 문제에 주어진 순서대로 구현하는 되는 문제였다.

 

---

[참고서적]

이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈