[JAVA] 알고리즘 스터디 1주차 공통 과제: 괄호 변환 | 2020 KAKAO BLIND RECRUITMENT

2020 KAKAO BLIND RECRUITMENT 괄호 변환 level2

프로그래머스

🔒 문제

'('와 ')' 로만 이루어진 문자열이 있을 경우, '('의 개수와 ')'의 개수가 같다면 이를 균형 잡힌 괄호 문자열이라고 부릅니다.
그리고 여기에 '('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열이라고 부릅니다.
예를 들어, "(()))("와 같은 문자열은 "균형 잡힌 괄호 문자열"이지만 "올바른 괄호 문자열"은 아닙니다.
반면에 "(())()"와 같은 문자열은 "균형 잡힌 괄호 문자열" 이면서 동시에 "올바른 괄호 문자열"입니다.
'('와 ')' 로만 이루어진 문자열 w가 "균형 잡힌 괄호 문자열"이라면 다음과 같은 과정을 통해 "올바른 괄호 문자열"로 변환할 수 있습니다.

 

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. 생성된 문자열을 반환합니다.

 

"균형 잡힌 괄호 문자열" p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 "올바른 괄호 문자열"로 변환한 결과를 return 하도록 solution 함수를 완성해 주세요.

 

---

🔎  풀이

문제를 이해하는 것부터 쉽지 않았다. 지문이 워낙 길고 구현 내용 설명이 복잡해서 어려움을 느꼈다. 뭔가 기발한 알고리즘이나 새로운 자료구조를 배울 것을 기대했는데 그런 것은 하나도 없었고, 정말 단순히 뇌를 빼고 구현하라는 대로 그대~로 구현했더니 풀렸다. 나는 메서드를 각 기능에 따라 분리해서 총 세 개를 구현했다. 

 

 

🔹makeCorrectBracket 

먼저 첫 번째는 주어진 문자열을 올바른 괄호 문자열로 변환하는 재귀함수 makeCorrectBracket이다. 해당 함수는 문제 설명에 있는 '코드 블록'을 그대로 정말 말 그대로 똑같이 구현하면 된다. 코드 블록의 한 줄 한 줄을 주석으로 달아놨으니 참고하면 좋을 것 같다.

 

    /*
    // 주어진 문자열을 올바른 괄호 문자열로 변환하는 재귀함수
    // @param s: [String] 주어진 문자열 s
    // @return [String] 주어진 문자열 s를 올바른 괄호 문자열로 변환한 결과
    */
    public String makeCorrectBracket( String s ){

	// 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환
        if( s.isEmpty() ) return s;

	// 2. 문자열 s를 두 "균형잡인 괄호 문자열" u,v로 분리
        String[] strings = splitString(s);
        String u = strings[0];
        String v = strings[1];

        StringBuilder correctString = new StringBuilder();
	
        if(checkIfCorrect(u)){ // 3. 문자열 u가 올바른 괄호 문자열인 경우
        
            correctString.append(u);
            
           // 3-1. v를 1단계부터 다시 수행하고, 그 결과를 u에 이어 붙인다.
            correctString.append(makeCorrectBracket(v));
            
        }
        else{ // 4. 문자열 u가 올바른 괄호 문자열이 아닌 경우
            
            // 4-1. 괄호 열기
            correctString.append('(');

            // 4-2. v를 1단계부터 재귀 수행 후 이어 붙이기
            correctString.append(makeCorrectBracket(v));

            // 4-3. 괄호 닫기
            correctString.append(')');

            // 4-4. u 맨 앞뒤 지우고, 괄호 뒤집어서 붙이기
            for( int i = 1; i < u.length()-1; i++ ){
                if( u.charAt(i) == ')') correctString.append('(');
                else correctString.append(')');
            }
        }
		
        // 3-2, 4-5. 생성된 문자열 반환
        return correctString.toString();

    }

 

🔹 splitString

makeCorrectBracket 함수에서는 주어진 균형 잡힌 괄호 문자열 s를 두 개의 균형 잡힌 괄호 문자열 u, v로 분리하는 과정이 필요하다. 이때 조건은 두 개로 나눈 문자열 중 첫 번째 문자열인 u는 균형 잡힌 괄호 문자열로 더 이상 분리할 수 없어야 하고, v는 빈 문자열이 될 수 있다는 것이다. 

즉, 문자열 s를 index= 0부터 순회하며 여는 괄호 개수와 닫는 괄호 개수가 처음으로 같아지는 바로 그 시점이 나누는 시점인 것이다. 그리고 split 변수에 해당 '인덱스 + 1'한 값을 담는다. 해당 인덱스에 1을 더해야 substring 할 때 u의 범위를 0부터 해당 인덱스(split - 1)까지로 설정할 수 있다.  

그리고 나머지 v는 split부터 끝까지 담는다. 

 

    /*
    // 주어진 문자열을 두 개의 균형잡인 괄호 문자열로 분리하는 함수
    // @param s: [String] 주어진 문자열 s
    // @return [String[]] 주어진 문자열 s를 균형잡인 두 개의 괄호 문자열로 나눈 결과
     */
    public String[] splitString( String s ){

        String[] strings = new String[2];

        int open = 0; // 여는 괄호 개수
        int close = 0; // 닫는 괄호 개수
        int split = 0; // 문자열 두 개로 나누는 지점

        for( int i = 0; i < s.length(); i++ ){
            char bracket = s.charAt(i);

            if( bracket == '(') open++;
            else close++;

            if( open == close ) {
                split = i + 1;
                break;
            }
        }

        strings[0] = s.substring(0,split);
        strings[1] = s.substring(split);

        return strings;

    }

 

 

🔹checkIfCorrect 

makeCorrectBracket 함수에서는 분리한 문자열 u가 "올바른 괄호 문자열"인지 판단하는 과정이 필요하다. 나는 이를 따로 분리해 checkIfCorrect 메서드를 사용해서 확인한다. 괄호가 짝이 맞는지 확인해서 짝이 맞으면 true, 그렇게 않으면 false를 반환한다.

 

    /*
    // 주어진 문자열이 올바른 괄호 문자열인지 확인
    // @param s: 주어진 문자열 s
    // @return [boolean]: 올바른 괄호 문자열이면 true
     */
    public boolean checkIfCorrect( String s ){
        int open = 0;

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

            else open++;
        }

        return true;
    }

 

---

 

🔐 전체 코드

 

class Solution {

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

    /*
    // 주어진 문자열을 올바른 괄호 문자열로 변환하는 재귀함수
    // @param s: [String] 주어진 문자열 s
    // @return [String] 주어진 문자열 s를 올바른 괄호 문자열로 변환한 결과
    */
    public String makeCorrectBracket( String s ){

	// 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환
        if( s.isEmpty() ) return s;

	// 2. 문자열 s를 두 "균형잡인 괄호 문자열" u,v로 분리
        String[] strings = splitString(s);
        String u = strings[0];
        String v = strings[1];

        StringBuilder correctString = new StringBuilder();
	
        if(checkIfCorrect(u)){ // 3. 문자열 u가 올바른 괄호 문자열인 경우
        
            correctString.append(u);
            
           // 3-1. v를 1단계부터 다시 수행하고, 그 결과를 u에 이어 붙인다.
            correctString.append(makeCorrectBracket(v));
            
        }
        else{ // 4. 문자열 u가 올바른 괄호 문자열이 아닌 경우
            
            // 4-1. 괄호 열기
            correctString.append('(');

            // 4-2. v를 1단계부터 재귀 수행 후 이어 붙이기
            correctString.append(makeCorrectBracket(v));

            // 4-3. 괄호 닫기
            correctString.append(')');

            // 4-4. u 맨 앞뒤 지우고, 괄호 뒤집어서 붙이기
            for( int i = 1; i < u.length()-1; i++ ){
                if( u.charAt(i) == ')') correctString.append('(');
                else correctString.append(')');
            }
        }
		
        // 3-2, 4-5. 생성된 문자열 반환
        return correctString.toString();

    }

    /*
    // 주어진 문자열이 올바른 괄호 문자열인지 확인
    // @param s: 주어진 문자열 s
    // @return [boolean]: 올바른 괄호 문자열이면 true
     */
    public boolean checkIfCorrect( String s ){
        int open = 0;

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

            else open++;
        }

        return true;
    }


    /*
    // 주어진 문자열을 두 개의 균형잡인 괄호 문자열로 분리하는 함수
    // @param s: [String] 주어진 문자열 s
    // @return [String[]] 주어진 문자열 s를 균형잡인 두 개의 괄호 문자열로 나눈 결과
     */
    public String[] splitString( String s ){

        String[] strings = new String[2];

        int open = 0; // 여는 괄호 개수
        int close = 0; // 닫는 괄호 개수
        int split = 0; // 문자열 두 개로 나누는 지점

        for( int i = 0; i < s.length(); i++ ){
            char bracket = s.charAt(i);

            if( bracket == '(') open++;
            else close++;

            if( open == close ) {
                split = i + 1;
                break;
            }
        }

        strings[0] = s.substring(0,split);
        strings[1] = s.substring(split);

        return strings;

    }

}

 

 

끝.

감사합니다.