괄호 변환 2020 KAKAO BLIND RECRUITMENT [자바]

 

🧫 문제 분석

✔️ 출처

괄호 변환

📖 문제

 

구현 문제

 

주어진 괄호 문자열을 올바른 괄호 문자열로 변환한다.

1. 주어진 문자열이 올바른 문자열 검증

2. 최소 균형잡힌 괄호 범위를 구하여 u, v로 나눔

2-1. u가 올바른 문자열이라면 v를 다시 1번부터 반복하고 더이상 쪼개기가 불가능하다면 u + v를 반환

2-2. u가 올바르지 않다면 u의 맨 앞과 맨 뒤를 없애고, u의괄호를 다 뒤집은 뒤  '(' + v + ')'  + reverseU 로 반환

2-3. v는 1번부터 반복

 

 

재밌는 문제였다. 

어떻게하면 괄호가 올바른 문자열인지 빠르게 구할까, 미리 메모이제이션해놓을까 했지만

문자열 길이가 1000이하 이므로 굳이 하지 않았다. 

 

실수하기 좋은게 내 풀이에서 시작을 v메서드로 시작하고, 탐색 범위를 s, e로 제한하고 i로 탐색하는데

이걸 실수해서 초반에 좀 틀렸다. 

 

범위 탐색 문제의 경우 범위 값을 잘 확인하자.

 

 

올바른 문자열 판별을 처음에 stack으로 했는데 다른사람 풀이를 보고 배웠다.

단순 카운트만으로 판별하는 건데

int open 으로 여는 괄호 개수를 기준으로 판단한다.

열림 괄호면 +1

닫힘 괄호면 -1

 

이때 닫힘 괄호 연산 전 open이 0이면 

이미 부분 문자열에서 올바른 괄호의 조건에서 벗어난 것이다.

이로써 굳이 자료구조를 쓰지 않고 빠르게 구할 수 있다. 

 

 

---

🔅 문제 풀이

class Solution {
    char[] arr;
    
    public String solution(String p) {
        arr = p.toCharArray();
        
        // 2. 올바른 괄호 문자열 변환 로직
        return v(0, arr.length - 1);
    }
    
    // 괄호 방향 뒤집기 
    private String reverse(int s, int e) {
        if (e == arr.length - 1) {
            return "";
        }
        
        StringBuilder sb = new StringBuilder();
        
        for (int i = s; i <= e; i++) {
            if (arr[i] == ')') arr[i] = '(';
            else arr[i] = ')';
            
            sb.append(arr[i]);
        }
        
        return sb.toString();
    }
    
    // u v 나누고 합치는 연산 
    private String v(int s, int e) {
        if (s >= arr.length) {
            return "";
        }
        
        // 1. 올바른 괄호 문자열 판단
        if (isAlright(s, e)) {
            return charToString(s, e);
        }
        
        int open = 0, close = 0;
        for (int i = s; i <= e; i++) {
            if (arr[i] == '(') open++;
            else close++;
            
            // 3-1. u를 균형잡힌 괄호 문자열로 분리 
            // u가 더이상 분리 불가 균형잡힌 괄호 문자열이여야함
            if (open == close) {
                String v = v(i+1, e);
                
                if (isAlright(s, i)) {
                    String u = charToString(s, i);
                    return u + v;
                }
                
                String reverseU = reverse(s + 1, i - 1);
                return "(" + v + ")" + reverseU;
            }
        }
        
        return "";
    }
    
    private boolean isAlright(int s, int e) {
        int open = 0;
        
        for (int i = s; i <= e; i++) {
            char c = arr[i];
            if (c == ')') {
                if (open == 0) return false;
                open--;
            } else {
                open++;
            }
        }
        
        return true;
    }
    
    private String charToString(int s, int e) {
        StringBuilder sb = new StringBuilder();
        for (int i = s; i <= e; i++) {
            sb.append(arr[i]);
        }
        
        return sb.toString();
    }
}

 

 

🔅 리팩토링

❗ 오답노트 / 필요한 지식

1. 범위 탐색 문제의 경우 범위 값을 잘 확인하자