[알고리즘]프로그래머스 60058번 - 괄호 변환

프로그래머스 60058번 - 괄호 변환

프로그래머스 60058번 - https://programmers.co.kr/learn/courses/30/lessons/60058

프로그래머스 60058번 - https://programmers.co.kr/learn/courses/30/lessons/60058

 

요구사항

1. 문자열이 '('와 ')'로 이루어져있을 때 '('의 개수와 ')'의 개수가 같다면 균형잡힌 괄호 문자열이다.

2. 균형잡힌 괄호 문자열이면서 '('와 ')'의 괄호 짝도 모두 맞을 경우에는 올바른 괄호 문자열이다.

3. 주어진 방법대로 균형잡힌 문자열을 올바른 괄호 문자열로 바꾸어서 반환하라.

 

요구사항 분석 및  풀이과정

1. 균형잡힌 괄호 문자열인지 검사를 하는 방법은 '(' 문자가 나올 경우 +1, ')' 문자가 나올 경우 -1을 하여 결과가 0인지를 확인하면 된다.

2. 올바른 괄호 문자열인지 검사를 하는 방법 또한 1번과 동일하나 +1, -1을 한 결과가 음수가 되면 짝이 맞지 않는 시점이 발생했다는 것이므로 올바른 괄호 문자열이 될 수 없다는 것을 의미한다. 

3. 우리는 균형잡힌 문자열을 올바른 괄호 문자열로 바꾸는 방법 중 문자열을 두 균형잡힌 괄호 문자열로 분해를 하여야하는데, 이 때 분해된 문자열 u, v 중 u는 더이상 분해할 수 없는 균형잡힌 괄호 문자열이여야 한다.

4. 그렇기 때문에, 1번에서 균형잡힌 괄호 문자열인지를 검사를 하면서 처음으로 균형잡히는 시점(+1, -1한 결과가 0인 시점) 때의 위치를 반환하여 주도록 할 것이다. 그 위치를 기점으로 문자열을 나누면 조건에 맞게 두 균형잡힌 괄호 문자열로 나눌 수 있다.

5. 나머지는 주어진 방법대로 옮기면 된다.

 

소스코드 작성

class Solution {

    private boolean valid(String p) {
        int count = 0;

        for(char v : p.toCharArray()) {
            count += (v == '(' ? 1 : -1);
            
            if (count < 0) {
                return false;
            }
        }
        
        return true;
    }
    
    private int balancedPos(String p) {
        char[] chars = p.toCharArray();
        int count = 0;
        
        for(int i = 0; i < chars.length; i++) {
            count += (chars[i] == '(' ? 1 : -1);
            
            if (count == 0) {
                return i + 1;
            }
        }
        
        return -1;
    }
    
    private String inverse(String p) {
        char[] chars = p.toCharArray();
        
        for(int i = 0; i < chars.length; i++) {
            chars[i] = chars[i] == ')' ? '(' : ')';
        }
        
        return String.valueOf(chars);
    }
    
    private String make(String p) {   
        if ("".equals(p)) {
            return "";
        }
        
        int balancedPos = balancedPos(p);
        String u = p.substring(0, balancedPos);
        String v = p.substring(balancedPos);
        
        if (valid(u)) {
            return u + make(v);
        } else {
            return "(" + make(v) + ")" + inverse(u.substring(1, u.length() - 1));
        }
    }
    
    public String solution(String p) {
        return make(p);
    }
}

 

결과

 

소스코드 깃허브 주소

링크