2020 KAKAO BLIND RECRUITENT : 괄호 변환

*** 본 풀이는 java 언어를 사용하였습니다. ***

문제 보러가기

 

핵심 요약

균형잡힌 괄호 문자열 p를 입력받으면, 올바른 괄호 문자열로 변환하라

 

규칙 설명이 상세하게 잘 되어있어, 규칙대로 하나씩 차근차근 만들어 나가면 무리없이 문제를 풀 수 있을 것이라 생각한다.

규칙은 다음과 같다.

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 

2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 
   단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 

3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
   3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 

4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
   4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
   4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
   4-3. ')'를 다시 붙입니다. 
   4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
   4-5. 생성된 문자열을 반환합니다.

 

여기서 중요한 점은 크게 2가지이다.

1. 규칙 2.에서 u, v로 분리를 할 때, u는 더 이상 분리할 수 없는 상태여야 한다는 것이다.
   쉽게 말하면 '(' 의 개수와 ')'의 개수가 최초로 같아지는 시점으로 분리를 하면 된다.
2. 재귀에 대한 이해

 

하지만 필자는 재귀에 대한 이해가 완벽히 되지 않아 초반에 다음과 같이 구현하여 실수를 범했다.

private StringBuilder sb = new StringBuilder();

public String solution(String p) {
    ...
   
    // 올바른 괄호 문자열인가
    if (isCorrect(divisionText[0])) {
        sb.append(divisionText[0]);
        sb.append(solution(divisionText[1]));
    }
    
    ...
    
    return sb.toString();
}

만약 p = "()" 일 경우 예상대로라면 "()"를 리턴해야 한다.

하지만 결과는 "()()" 가 나온다.

sb.append(solution(divisionText[1]));

solution() 메서드에는 출력을 리턴하는 로직이 있다.

재귀로 solution() 메서드를 다시 호출하면서 sb.toString()을 두번 리턴하기 때문에 결과가 다르게 나온것이다.

 

이 문제를 해결하려면 다음과 같이 코드를 수정해야 한다.

// 올바른 괄호 문자열인가
if (isCorrect(divisionText[0])) {
    return divisionText[0] + solution(divisionText[1]);
}

 

제출 코드

import java.util.EmptyStackException;
import java.util.Stack;

public class Solution {
    public String solution(String p) {
        if (p.isEmpty()) return p;
        String[] divisionText = division(p); // divisionText[0] = u, divisionText[1] = v
        if (isCorrect(divisionText[0])) {
            return divisionText[0] + solution(divisionText[1]);
        }
        return makeNotCorrectCaseText(divisionText);
    }

    private String makeNotCorrectCaseText(String[] divisionText) {
        StringBuilder sb = new StringBuilder();
        sb.append("(");
        sb.append(solution(divisionText[1]));
        sb.append(")");
        sb.append(reverseText(deleteFirstAndLastText(divisionText[0])));
        return sb.toString();
    }

    private String reverseText(String text) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < text.length(); i++) {
            if (text.charAt(i) == '(') {
                sb.append(')');
            } else {
                sb.append('(');
            }
        }
        return sb.toString();
    }

    private String deleteFirstAndLastText(String text) {
        return text.substring(1, text.length() - 1);
    }

    private boolean isCorrect(String u) {
        Stack<Character> stack = new Stack<>();
        try {
            for (int i = 0; i < u.length(); i++) {
                char text = u.charAt(i);
                if (text == '(') {
                    stack.add(text);
                } else {
                    stack.pop();
                }
            }
        } catch (EmptyStackException e) {
            return false;
        }
        return true;
    }

    private String[] division(String p) {
        int endIndex = endIndex(p);
        String u = p.substring(0, endIndex);
        String v = p.substring(endIndex);
        return new String[]{u, v};
    }

    public int endIndex(String p) {
        int openCount = 0;
        int closeCount = 0;
        int size = p.length();

        for (int i = 0; i < size; i++) {
            char text = p.charAt(i);
            if (text == '(') {
                openCount++;
            } else {
                closeCount++;
            }

            if ((openCount > 0 && closeCount > 0) && openCount == closeCount) {
                return i + 1;
            }
        }
        return size;
    }
}

 

테스트 코드

import org.junit.Before;
import org.junit.Test;

import static org.assertj.core.api.Assertions.assertThat;

public class SolutionTest {
    private Solution solution;

    @Before
    public void setUp() throws Exception {
        solution = new Solution();
    }

    @Test
    public void testCase_1() {
        assertThat(solution.solution("(()())()")).isEqualTo("(()())()");
    }

    @Test
    public void testCase_2() {
        assertThat(solution.solution(")(")).isEqualTo("()");
    }

    @Test
    public void testCase_3() {
        assertThat(solution.solution("()))((()")).isEqualTo("()(())()");
    }

    @Test
    public void testCase_4() {
        assertThat(solution.solution("()")).isEqualTo("()");
    }

    @Test
    public void 쪼갤수있는_문자열이_잘_분리됬는가() {
        // given
        String p = "))((()";

        // when
        int endIndex = solution.endIndex(p);

        // then
        assertThat(p.substring(0, endIndex)).isEqualTo("))((");
        assertThat(p.substring(endIndex)).isEqualTo("()");
    }

    @Test
    public void 쪼갤수없는_문자열이_잘_분리됬는가() {
        // given
        String p = ")(";

        // when
        int endIndex = solution.endIndex(p);

        // then
        assertThat(p.substring(0, endIndex)).isEqualTo(")(");
        assertThat(p.substring(endIndex)).isEqualTo("");
    }
}

 

회고

문제를 봤을때는 그렇게 어려운 문제는 아니라고 생각했는데, 재귀를 잘못사용하여 엉뚱한 String을 반환해버리는 멍청한 실수를 저지르고 말았다.. 이 문제 때문에 거진 1시간 동안 푼 것같다.. 에효 다음에는 실수하지 말자.

필자는 알고리즘도 리팩토링을 통해서 구현하자는 의식적인 연습을 수행중이다.

코드를 보면 알겠지만 메서드가 하나의 일을 하도록 분리한 것을 볼 수 있을것이다.

이렇게 분리한 이유는 다음과 같다.

코드의 재사용성을 높일 수 있다.

해당 코드를 처음보는 개발자가 메서드 이름만 보고도 메서드의 역할을 유추하기 쉽다.

테스트 케이스를 작성하기 쉽다.

아직 완벽하게 리팩토링을 하지는 않았지만 이런 의식적인 연습을 꾸준히 하면 좋은 습관이 몸에 베이게 될 것이고,

앞으로 코딩을 하는데 있어 분명히 도움이 되리라 생각하기 때문에 무작정 푸는 것보다 코드의 품질도 생각하면서 코딩했으면 좋겠다.

더불어 테스트 케이스를 작성해 둔다면, 알고리즘 로직을 변경할 때에도 테스트를 돌리면 코드가 제대로 동작하는지 검증이 되기 때문에 테스트 케이스도 꾸준히 작성하는 것을 추천한다.