18.괄호 변환

📍 문제 설명

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

코딩테스트 연습 - 괄호 변환

💡 접근

문제에서 요구하는 순서대로만 구현하면 되는 문제였다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);

        String p = kb.nextLine();
        System.out.println(solution(p));
    }

    private static String solution(String p) {
        //올바른 괄호 문자열은 '('의 갯수와 ')'의 갯수만 동일한 것
        //균형잡힌 문자열은 poll 해야하는데 할게 없거나 사이즈가 남는 것
        String answer = "";
        if(p.equals("")) return answer;

        String u = "";
        String v = "";
        int cnt = 0;

        //문자열 분리
        for(int i = 0; i < p.length(); i++) {
            if(p.charAt(i) == '(') cnt++;
            else cnt--;
            //균형잡힌 괄호 문자열 찾았으면 바로 끝내!
            if(cnt == 0) {
                u = p.substring(0, i+1);
                v = p.substring(i+1);
                break;
            }
        }

        //u가 올바른 괄호 문자열이면 v에 대해서 재귀적으로 다시 처리!
        if(properString(u)) {
            answer = u + solution(v);
        }
        //u가 올바른 괄호 문자열이 아니면 다른 처리!
        else {
            answer = "(";
            //v에 대해서 재귀적으로 수행한 결과 붙이기
            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;
    }

    //올바른 괄호 문자열인지 판단
    private static boolean properString(String p) {
        Queue<Character> q = new LinkedList<>();

        boolean flag = true;

        for(int i = 0; i < p.length(); i++) {
            //여는 괄호는 무조건 큐에 삽입
            if(p.charAt(i) == '(') q.offer('(');
            //닫는 괄호면 여는 괄호를 poll
            else {
                //poll시킬게 없으면 올바른 괄호 문자열이 아니다.
                if(q.size() == 0) {
                    flag = false;
                    break;
                }
                q.poll();
            }
        }
        if(q.size() == 0) return flag;
        else return false;
    }


}