[2020 KAKAO BLIND RECRUITMENT] 괄호 변환 - JAVA

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

프로그래머스

---

이 문제는 이해하는데 오래 걸려서 문제 설명을 좀 자세하게 써보려고 한다

 

우선 문제에서의 용어와 정의를 정리해보자

 

균형잡힌 괄호 문자열 : ( 와 ) 의 개수만 같으면 된다

올바른 문자열 : ( 와 ) 의 짝이 맞는다

 

문제에서 주어지는 문자열은 균형 잡힌 문자열이고, 이를 올바른 괄호 문자열로 변환하는 것이 핵심이다!

이를 변환하는 방법은 문제에서 주어진다

 

 

변환 방법

• 요건 그냥 빈 문자열이면 고대로 반환하면 된다

 

• 문자열 w는 주어진 문자열이다
• 이를 u와 v로 분리하면 되는데, u는 더 이상 분리할 수 없어야 하기 때문에 가장 작은 단위로 분리해야 한다
• 즉, ( 와 )의 개수가 처음 같아지는 순간을 의미한다!
• 그러면 남은 문자열이 자연스럽게 v가 된다

 

• 2번에서 분리한 문자열 u가 올바른 괄호 문자열이면, 문자열 v에 대해 다시 1단계부터 수행한다
• 그리고 v에 대해서 수행한 결과는 u에 붙인 후 반환하면 된다

 

• 3번과 달리 자른 문자열 u가 올바른 괄호 문자열이 아니면 수행하면 된다

---

저 과정들을 이해하는 것도 어려웠고 이해한 내용을 구현하는 것도 쉽지 않았다,,,

그래도 한번 풀리니까 쭉 풀리는 문제였다!!

 

 

 

자바 코드)

import org.junit.Assert;
import org.junit.Test;

public class ConversionBracket {
    public String solution(String p) {
        String answer = p;
        if(check(answer)) {
            return answer;
        }

        answer = split(answer);
        return answer;
    }

    // 올바른 문자열인지 판단하는 메소드
    private static boolean check(String s) {
        // 첫 문자가 ) 이면 올바르지 않은 문자열임
        if(s.charAt(0)==')') {
            return false;
        }

        int open = 1; // ( 의 개수

        for(int i=1;i<s.length();i++) {
            if(s.charAt(i)=='(') {
                open++;
            } else {
                open--;
                // (의 개수가 0보다 작으면 짝이 맞지 않으므로 올바르지 않은 문자열임
                if(open<0) {
                    return false;
                }
            }
        }
        // 위의 단계를 모두 통과하면 올바른 문자열임
        return true;
    }

    // u, v 분리 메소드
    private static String split(String s) {
        // 빈 문자열인 경우, 그대로 반환
        if(s.length()==0) {
            return s;
        }

        StringBuilder u = new StringBuilder();
        StringBuilder v = new StringBuilder();

        int open = 0;
        for(int i=0;i<s.length();i++) {
            if(s.charAt(i)=='(') {
                open++;
            } else {
                open--;
            }

            // 처음으로 '('의 개수가 0이 된 경우가 가장 작은 단위의 균형잡힌 문자열이다
            if(open==0) {
                // 현재 i를 기준으로 u와 v를 분리
                u.append(s, 0, i+1);
                v.append(s.substring(i+1));

                // u가 올바른 문자열인지 확인
                if(check(u.toString())) {
                    // v에 대해 재귀호출 후, u에 이어 붙인다
                    u.append(split(v.toString()));
                } else { // 4. u가 올바른 문자열이 아닌 경우
                    StringBuilder str = new StringBuilder();
                    str.append("(");
                    str.append(split(v.toString()));
                    str.append(")");
                    // u를 조작해서 붙인다
                    str.append(reverse(u.toString()));
                    return str.toString();
                }
                break;
            }
        }
        // u가 올바른 문자열인 경우 반환된다
        return u.toString();
    }

    // u 문자열을 변환하는 메소드
    private static String reverse(String u) {
        StringBuilder s = new StringBuilder();

        for(int i=1;i<u.length()-1;i++) {
            // 괄호를 뒤집어서 문자열에 붙여준다
            if(u.charAt(i)=='(') {
                s.append(")");
            } else {
                s.append("(");
            }
        }
        return s.toString();
    }

    @Test
    public void test() {
        Assert.assertEquals("(()())()", solution("(()())()"));
        Assert.assertEquals("()", solution(")("));
        Assert.assertEquals("()(())()", solution("()))((()"));
    }
}

 

 

---

참고)

https://fbtmdwhd33.tistory.com/250

[프로그래머스,Level 2] 괄호 변환 (JAVA 구현)