[프로그래머스] 괄호 변환(2020 KAKAO BLIND RECRUITMENT)

 

2020년 카카오 채용 코테에 출제된 괄호 변환 문제를 풀어보았습니다.

 

 

이 문제는 조금 특이하게 문제에서 알고리즘이 주어지고, 주어진 알고리즘대로 소스 코드를 구현하면 되는 문제였습니다.

위 규칙에 따라서 코딩을 하면 되는 문제인데, 생각해보아야 할 것은 다음과 같습니다.

 

1. 올바른 괄호/균형 잡힌 괄호 판단 기준

2. 재귀 함수 처리

 

1. 올바른 괄호/균형 잡힌 괄호 판단

균형 잡힌 괄호는 단순히 여는 괄호'('와 닫는 괄호')'의 개수가 동일한 경우이므로 판단이 어렵지 않았습니다.

올바른 괄호는 여는 괄호와 닫는 괄호의 쌍이 순서에 맞게 이루어져야하므로 Stack을 활용해서 판단했습니다.

public String chapterTwo(int strLen, String p){
        int balance = 0;
        String u = "";
        String v = "";
        for(int i=0; i<strLen; i++){
            if(p.charAt(i)=='(') {
                balance++;
            }else if(p.charAt(i)==')') {
                balance--;
            }
            if(balance==0) {
                u = p.substring(0, i+1);
                v = p.substring(i+1, p.length());
                break;
            }
        }
        if(checkPair(u.length(), u)) {
             // 올바른 괄호 문자열
             if(v.length()==0) return u;
             return u+chapterTwo(v.length(), v);
         }else {
             // 균형잡힌 괄호 문자열
             StringBuffer sb = new StringBuffer();
             sb.append("(");
             sb.append(chapterTwo(v.length(), v));
             sb.append(")");
             String tempStr = u.substring(1, u.length()-1).replaceAll("[(]", "O").replaceAll("[)]", "C");
             String reverseStr = tempStr.replaceAll("[O]", ")").replaceAll("[C]", "(");
             return sb.append(reverseStr).toString();
         }
    }
    public boolean checkPair(int strLen, String p){
        for(int i=0; i<strLen; i++){
            if(p.charAt(i)=='(') st.push(p.charAt(i));
            else if(p.charAt(i)==')') {
                if(st.isEmpty()) return false;
                st.pop();
            }
        }
        if(st.isEmpty()) return true;
        return false;
    }

 

2. 재귀 함수 처리

어떠한 로직을 반복해서 처리해야하는 경우 재귀 함수를 활용할 수 있는데, 문제에서 주어진 조건 중 3번, 4-2번 동작을 수행하는 데 있어서 재귀 함수가 필요했습니다.

if(checkPair(u.length(), u)) {
    // 올바른 괄호 문자열
    if(v.length()==0) return u;
    return u+chapterTwo(v.length(), v);
}else {
    // 균형잡힌 괄호 문자열
    StringBuffer sb = new StringBuffer();
    sb.append("(");
    sb.append(chapterTwo(v.length(), v));
    sb.append(")");
    String tempStr = u.substring(1, u.length()-1).replaceAll("[(]", "O").replaceAll("[)]", "C");
    String reverseStr = tempStr.replaceAll("[O]", ")").replaceAll("[C]", "(");
    return sb.append(reverseStr).toString();
}

 

전체 코드

import java.util.*;
class Solution {
    static Stack<Character> st = new Stack<>();
    public String solution(String p) {
        int strLen = p.length();
        if(strLen==0) return p;
        if(checkPair(strLen, p)) return p;
        String result = chapterTwo(strLen, p);
        return result;
    }
    public String chapterTwo(int strLen, String p){
        int balance = 0;
        String u = "";
        String v = "";
        for(int i=0; i<strLen; i++){
            if(p.charAt(i)=='(') {
                balance++;
            }else if(p.charAt(i)==')') {
                balance--;
            }
            if(balance==0) {
                u = p.substring(0, i+1);
                v = p.substring(i+1, p.length());
                break;
            }
        }
        if(checkPair(u.length(), u)) {
            // 올바른 괄호 문자열
            if(v.length()==0) return u;
            return u+chapterTwo(v.length(), v);
        }else {
            // 균형잡힌 괄호 문자열
            StringBuffer sb = new StringBuffer();
            sb.append("(");
            sb.append(chapterTwo(v.length(), v));
            sb.append(")");
            String tempStr = u.substring(1, u.length()-1).replaceAll("[(]", "O").replaceAll("[)]", "C");
            String reverseStr = tempStr.replaceAll("[O]", ")").replaceAll("[C]", "(");
            return sb.append(reverseStr).toString();
	}
    }
    public boolean checkPair(int strLen, String p){
        for(int i=0; i<strLen; i++){
            if(p.charAt(i)=='(') st.push(p.charAt(i));
            else if(p.charAt(i)==')') {
                if(st.isEmpty()) return false;
                st.pop();
            }
        }
        if(st.isEmpty()) return true;
        return false;
    }
}