프로그래머스(괄호 변환)-스택, 구현

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

프로그래머스

1. 걸린 시간

50분

 

2. 트리거

옳은 괄호인지에 대해, stack을 사용하여, 확인한다.

나머지는 재귀로 그냥 조건을 따라치면 되는 쉬운 문제이다.

 

조건을 잘 못 읽어 오래걸렸다...

StringBuilder로 최적화 또한 가능하겠다.

import java.util.*;

//7:50
class Solution {
    public String solution(String p) {
        String answer = solve(p);
        return answer;
    }
    
    private String solve(String p) {
        if(isRight(p)) return p;
        return recursive(p);
    }
    
    private String recursive(String p) {
        if(p.equals("")) return "";
        String u = getU(p);
        String v = getV(u.length(), p);
        if(isRight(u)) {
            String result = recursive(v);
            return u + result;
        }
        
        String newStr = "(" + recursive(v) + ")";
        String newU = reverseU(u.substring(1, u.length()-1));
        return newStr + newU;
    }
    
    private String getU(String p) {
        int size = p.length();
        int aCnt = 0;
        int bCnt = 0;
        for(int i = 0; i < size; i++) {
            char c = p.charAt(i);
            if(c == '(') {
                aCnt++;
            } else {
                bCnt++;
            }
            if(aCnt != 0 && bCnt != 0 && aCnt == bCnt) return p.substring(0, aCnt + bCnt);
        }
        return p;
    }
    
    private String getV(int uSize, String p) {
        if(uSize == p.length()) return "";
        return p.substring(uSize, p.length());
    }
    
    private String reverseU(String u) {
        String result = "";
        int size = u.length();
        for(int i = 0; i < size; i++) {
            char c = u.charAt(i);
            if(c == '(') {
                result += ')';
                continue;
            }
            result += '(';
        }
        return result;
    }
    
    private boolean isRight(String u) {
        int size = u.length();
        Deque<Character> deque = new ArrayDeque<>();
        for(int i = 0; i < size; i++) {
            char c = u.charAt(i);
            if(c == '(') {
                deque.push(c);
                continue;
            }
            if(c == ')') {
                if(deque.isEmpty()) return false;
                if(deque.peek() == '(') deque.pop();
            }
        }
        
        if(!deque.isEmpty()) return false;
        return true;
    }
}