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

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

프로그래머스

코딩테스트 연습 > 2020 KAKAO BLIND RECRUITMENT > 괄호 변환

 

난이도: LEVEL2

알고리즘 유형: 구현(스택/재귀 활용)

 

문제에서 주는 요구 사항 그대로 구현하면 끝이다.

문자열에 대해서 해당 과정을 적용해서 반환한다. → 재귀 

 

해당 문자열이 올바른 괄호인지 파악은 스택을 활용했다. 

아마 스택 관련 문제에서는 단순하게 해당 문자열이 올바른 괄호인지 파악하는 문제가 있었던 걸로 기억한다. 

 

주석에 요구 사항에 적힌 단계와 똑같이 단계를 적어두었다. 

정답 코드 

import java.util.*;
class Solution {
    public String solution(String p) {
        return make(p);
    }
    public String make(String w){
        // 입력이 빈 문자열 -> 빈 문자열 반환 
        if(w.length() == 0) return "";
        
        // 문자열 u, v로 분리 
        int cnt1 = 0; int cnt2 = 0;
        int index = 0;
        for(int i = 0; i < w.length(); i++){
            if(w.charAt(i) == '(') cnt1++;
            else cnt2++;
            if(cnt1 == cnt2){
                index = i + 1;
                break;
            }
        }
        String u = w.substring(0, index);
        String v = w.substring(index, w.length());
        // 올바른 괄호 판별
        boolean flag = check(u);
        
        // 3-1 
        if(flag){
            return u + make(v);
        }
        // u가 올바른 괄호가 아닌 케이스 
        
        String temp = "("; // 4-1 
        temp += make(v); // 4-2
        temp += ")"; // 4-3
        String u2 = u.substring(1, u.length() - 1);  // 4-4 자르기
        
        // 4-4 괄호 뒤집기 
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < u2.length(); i++){
            if(u2.charAt(i) == '(') sb.append(')');
            else sb.append('(');
        }
        return temp + sb.toString();
    }
    // 올바른 괄호 판별 메소드 
    public static boolean check(String u){
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < u.length(); i++){
            char cur = u.charAt(i);
            if(cur == '(') stack.push(cur);
            else{
                if(stack.isEmpty()) return false;
                else if(stack.peek() == '(') stack.pop();
            }
        }
        return true;
    }
}