[2020 KAKAO BLIND RECRUITMENT] 괄호 변환

2020 KAKAO BLIND RECRUITMENT 괄호 변환

유형

• Queue

코드

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public String solution(String p) {
        if(isCorrect(p)) return p;
        else return makeCorrect(p);
    }
    
    private boolean isCorrect(String p) {
        if(p.charAt(0) != '(' || p.charAt(p.length() - 1) != ')') return false;

        Queue<Character> queue = new LinkedList<>();
        for (int i = 0; i < p.length(); i++) {
            char s = p.charAt(i);
            if(s == '(') queue.add(s);
            else if(s == ')') {
                if(queue.size() == 0) return false;
                else {
                    char poll = queue.poll();
                    if(poll != '(') {
                        return false;
                    }
                }
            }
        }
        
        if(queue.size() != 0) return false;
        
        return true;
    }

    private String makeCorrect(String p) {
        String answer = "";
        if(p.isEmpty()) return p;
        
        String u = findBalanced(p)[0];
        String v = findBalanced(p)[1];
        if(isCorrect(u)) {
            answer = u + makeCorrect(v);
        }
        else {
            String str = "(" + makeCorrect(v) + ")";
            u = u.substring(1, u.length() - 1);
            for (int i = 0; i < u.length(); i++) {
                char s = u.charAt(i);
                if(s == '(') str += ')';
                if(s == ')') str += '(';
            }
            answer = str;
        }
        
        return answer;
    }

    private String[] findBalanced(String p) {
        Queue<Character> queue = new LinkedList<>();
        String u = "", v = "";
        
        queue.add(p.charAt(0));
        for (int i = 1; i < p.length(); i++) {
            char peek = queue.peek();
            if(peek == p.charAt(i)) {
                queue.add(p.charAt(i));
            } else {
                queue.poll();
            }
            if(queue.size() == 0) {
                u = p.substring(0, i + 1);
                v = p.substring(i + 1);
                break;
            }
        }
        
        return new String[]{u, v};
    }
}