[프로그래머스] LV 2 괄호변환

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

프로그래머스

 

접근 방법

1. 결론은 문제에서 하란대로 하면된다 (근데 문제를 이해하기 힘들었다)
2. 문제의 핵심은 문자열을 받아 올바른 문자열로 바꾸는 메서드를 작성하는것이고 다음과 같은 흐름으로 구현할 수 있다
   1. 입력 문자열이 비었다면 빈문자열을 반환한다
   2. 입력 문자열을 u,v로 나눈다
      1. 입력 문자열을 선형탐색하며 처음으로 "균형 잡힌 문자열"이 되는 구간 = u
      2. 나머지 = v
   3. u 가 올바른 문자열이라면 출력 문자열에 u를 붙이고 v이를 다시 재귀로 돌린다
   4. 올바르지 않다면
      1. 출력 문자열에 ( 를 붙인다
      2. v를 재귀 돌려 나온 문자열을 붙인다
      3. 출력 문자열에 ) 를 붙인다
      4. u의 양 끝 문자열을 제외하고 여는 괄호( 라면 닫는 괄호) 를 붙인다

참고) 올바른 문자열 함수를 작성할때 보통 Stack을 많이 사용하는데 ArrayDeque으로 Stack을 구현하는것이 좋다.

이유는 Stack은 Vector 클래스를 확장하여 동기화 되어있어 알고리즘을 풀때 성능에 악영향이 생길 수 있다.

 

코드

import java.util.*;
class Solution {
    String ans="";
    public String solution(String p) {
        recur(p);
        return ans;
    }
    void recur(String s){
        if(s.isEmpty()){
            ans += "";
            return;
        }
        int idx = getIdx(s);
        String u = s.substring(0,idx);
        String v = s.substring(idx,s.length());
        
        if(check(u)){
            ans+= u;
            recur(v);  
        }else{
            ans += "(";
            recur(v);
            ans += ")";
            ans += change(u);
        }
    }
    String change(String s){
        String res = "";
        for(int i = 1; i < s.length() -1 ; i++){
            res += s.charAt(i) == '(' ? ")" : "(";
        }
        return res;
    }
    int getIdx(String p){
        int tmp = 0;
        for(int i = 0 ; i < p.length() ; i++){
            tmp += p.charAt(i) == '(' ? 1 : -1;
            if(tmp == 0) return i+1;
        }
        return p.length();
    }
    boolean check(String s){
        Deque<Character> stack = new ArrayDeque<>();
        
        for(char c: s.toCharArray()){
            if(c == '('){
                stack.push(c);
                continue;
            }else if(!stack.isEmpty() && stack.peek() == '('){
                stack.pop();
                continue;
            }
            return false;
        }
        
        if(!stack.isEmpty()) return false;
        
        return true;
    }
}