문제

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

풀이

문자열이 주어졌을 때 올바른 괄호 문자열을 반환하는 문제이다.

용어 정의부터 살펴보면 다음과 같다.
균형 잡힌 괄호 문자열 : '(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같은 문자열

올바른 괄호 문자열 : 균형 잡힌 괄호 문자열에서 괄호의 짝도 맞는 경우

그리고 주어진 균형 잡힌 괄호 문자열 -> 올바른 괄호 문자열로 다음과 같은 방법을 통해 변환해야 한다.

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번 조건에 따라 w를 균형잡힌 괄호 문자열 u, v로 분리해야 하는데 이 때 u는 더 이상 분리할 수 없어야 하므로 처음으로 균형 잡힌 구간을 나눠줘야 한다.

예를 들면 ()))((() 가 있을 때 처음으로 균형 잡힌 순간은 () 이고 ))(()(은 ))((이다.

즉 처음으로 균형 잡혔을 때는 처음을 제외하고 괄호의 개수가 같을 때이다. 이 구간을 기준으로 u와 v를 나눌 수 있으며 마지막이 균형 잡힌 지점이라면 u = 전체 문자열, v = ""이 된다.

나누는 위치 찾는 코드는 다음과 같다.

int getDividePos(String p){
      int lCnt = 0;
      int rCnt = 0;
      for(int i = 0 ; i < p.length();i++){
          if(p.charAt(i) == '(')
              lCnt++;
          else
              rCnt++;

          if(lCnt == rCnt){
              return i;
          }
      }
      return p.length();
  }

2번 과정을 수행했다면 3번 조건인 올바른 괄호 문자열인지 검사한다.

boolean isCorrect(String p){
        int open = 0;

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

isCorrect가 true라면 올바른 문자열이므로 3-1을 수행하고(v를 재귀) 반환하면 된다.

만약 isCorrect가 false라면 올바르지 않은 문자열이므로 4번 과정을 수행하고 생성된 문자열을 반환하면 된다.

첫 번째로 문제를 이해하는데 굉장히 시간이 많이 썼다.
단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 2번 조건을 '(' 개수와 ')' 개수가 처음으로 같을 때라는 해석을 하지 못하여 시간이 걸렸다.
두 번째로 자바 String 메서드에 대해 익숙하지 않아 시간을 많이 썼다.

나머지 조건들은 문제에서 시키는 대로만 정확히 구현하면 되는 문제였다.

코드로 무작정 옮기기 전에 문제에 대한 해석을 정확히 하는 연습을 해야겠다.

코드

boolean isCorrect(String p){
        int open = 0;

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

    int getDividePos(String p){
        int lCnt = 0;
        int rCnt = 0;
        for(int i = 0 ; i < p.length();i++){
            if(p.charAt(i) == '(')
                lCnt++;
            else
                rCnt++;

            if(lCnt == rCnt){
                return i;
            }
        }
        return p.length();
    }

    String recursive(String p){

        if(p.isEmpty()){
            return "";
        }

        int pos = getDividePos(p);

        String u = p.substring(0, pos + 1);
        String v = p.substring(pos + 1);

        if(isCorrect(u)){
            v = recursive(v);
            return u + v;
        }
        else{
            String temp = "(" + recursive(v) + ")";

            for(int i = 1;i < u.length() - 1;i++){
                if(u.charAt(i) == '('){
                    temp += ")";
                }
                else{
                    temp += "(";
                }
            }
            return temp;
        }
    }

    public String solution(String p) {
        return recursive(p);
    }