Don't give up!

[프로그래머스] 괄호 변환(java) 본문

Coding Test/Programmers

[프로그래머스] 괄호 변환(java)

Heang Lee 2021. 4. 30. 23:00

코딩테스트 연습 - 괄호 변환 | 프로그래머스 (programmers.co.kr)

 

코딩테스트 연습 - 괄호 변환

카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를

programmers.co.kr

문제해석

문제를 해결하기 위해 필요한 것은 균형잡힌 괄호 문자열 분리, 올바른 괄호 문자열 판단, 문자열 변환입니다.

균형잡힌 괄호 문자열을 올바른 괄호 문자열로 변경하는 방법은 이미 문제에서 주어져 있습니다.

균형잡힌 문자열은 '('와 ')'의 개수가 같은 문자열입니다. String의 문자를 순회하면서 개수가 같은 지점을 기준으로 분리할 수 있을 것입니다.

가장 안쪽 괄호는 열린 괄호 직후 닫힌 괄호로 나타나야 올바른 괄호 문자열이 될 수 있습니다.

따라서 문자열의 '( )' 패턴을 계속 제거해 나갔을 때 남는 문자열이 존재하지 않으면 올바른 문자열임을 알 수 있습니다.

 

풀이

class Solution {
    public String solution(String u) {
        if(u.length()==0) return "";
        int index = findIndex(u);
        String v = u.substring(index);
        u = u.substring(0,index);
        if(isValid(u)){
            return u+solution(v);
        }
        else{
            u = u.substring(1,u.length()-1);
            return "("+solution(v)+")"+reverse(u);
        }
    }
    public int findIndex(String u){
        int index=0, open=0, close=0, length=u.length();
        while(index<length){
            if(u.charAt(index)=='(') open++;
            else close++;
            index++;
            if(open==close) break;
        }
        return index;
    }
    public boolean isValid(String u){
        String temp = new String(u);
        int length = temp.length();
        while(length!=0){
            String excluded = String.join("",temp.split("\\(\\)"));
            if(excluded.length() ==length) return false;
            temp = excluded;
            length = temp.length();
        }
        return true;
    }
    public String reverse(String u){
        u = u.replace("(","a");
        u  = u.replace(")","(");
        return u.replace("a",")");
    }
} 

주어진 로직 순서에 따라 문자열 분할이 이루어질 위치를 알려주는 findIndex함수, 올바른 괄호 문자열인지 판단하는 isValid함수, 문자열 괄호 방향을 뒤집는 reverse 함수를 작성하였습니다.

 

정규표현식

split함수나 replaceAll함수는 정규표현식을 입력받아 처리합니다.

(, )의 문자는 메타 문자로서 다음의 정규 표현식에 저장되어 있기 때문에 함수에 사용하고자 할때 메타 문자가 아닌 검사할 문자로 인식시키는 처리(이스케이프 처리)가 필요합니다.

표현식 설명
. 임의의 character(모든 문자)
\d 0~9의 숫자
\D 숫자가 아닌 문자
\s 공백문자 ex) \t, \n, \x0B, \f, \r 
\S 공백문자를 제외한 나머지 문자
\w a-z, A-Z, 0-9의 문자
\W \w의 문자들을 제외한 나머지 문자
(~) ~의 문자들을 하나의 문자로 인식
[ ] 문자의 집합을 의미. ^, &&, | 과 같은 기호로 집합의 연산을 수행할 수 있음
~{ } ~의 문자가 반복된 횟수, { } 사이에는 반복횟수가 들어간다.
~에 \d와 같이 표현식이 있는 경우 범위를 의미.
~? ~의 문자가 하나 있거나 없음
~+ ~의 문자가 하나 이상 있음
^~ 문자열의 시작에 ~의 문자가 있음
~$ 문자열의 끝에 ~의 문자가 있음
\b 단어 사이의 공백
\B 단어가 아닌 문자 사이의 공백
\A 입력의 시작
\Z 문자열 종단 문자까지 받은 입력의 끝
\z 입력의 끝
\\~ ~의 메타문자를 검사할 문자로 인식. \\는 \문자를 의미

( )는 하나의 문자로 인식하려 하기 떄문에 단순히 정규표현식에 집어넣으면 ( )의 문자를 구분하지 않습니다.

( ( ) ) 또한 첫 괄호 안의 문자에서도 정규표현식이 사용되므로 ( )의 문자를 구분하지 않습니다.

\\(로 (를 인식해야할 문자로 만들고, \\)로 )를 인식해야할 문자로 만듦으로서 ( )의 패턴을 찾아내는 정규 표현식을 작성할 수 있습니다.

더 자세하고 다양한 정규표현식은 다음의 페이지에서 찾아보실 수 있습니다.

Pattern (Java Platform SE 7 ) (oracle.com)

 

Pattern (Java Platform SE 7 )

Enables canonical equivalence. When this flag is specified then two characters will be considered to match if, and only if, their full canonical decompositions match. The expression "a\u030A", for example, will match the string "\u00E5" when this flag is s

docs.oracle.com