[프로그래머스, 자바] 괄호변환

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

프로그래머스

1. 문제 핵심

1. 균형잡힌 괄호 문자열, 올바른 괄호 문자열의 정의 이해.
2. 균형잡힌 괄호 문자열 => 올바른 괄호 문자열로의 변환 이해.

 

---

2. 문제 접근

※균형잡힌 괄호 문자열 => 올바른 괄호 문자열의 과정으로 설명

코드 0.

if (p.length() == 0)
	return "";

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

 

코드 2.

cnt = 0;
//첫 문자에 대한 처리
if(p.charAt(0) == ')')
    cnt--;
else
    cnt++;

//u : 균형잡힌 괄호 문자열 만들기
for (int i = 1; i < p.length(); i++) {
    if(p.charAt(i) ==')')
        cnt--;
    else
        cnt++;
    //균형잡힌 괄호 문자열인 경우
    if(cnt == 0) {
 		//어디까지 균형잡힌 문자열인지 판별
        pos = i;
        break;
    }
}

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

 

코드 3.

//u가 올바른 괄호 문자열인 경우
if(p.charAt(0)=='(') {
    //u
    sb.append(p.substring(0, pos+1));
    //v에 대한 재귀적 수행
    tmp = solution(p.substring(pos+1,p.length()));
    //u에 이어 붙이기
    sb.append(tmp);
}

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

 

코드 4.

else {
    //4-1
    sb.append('(');
    //4-2
    tmp =solution(p.substring(pos+1,p.length()));
    sb.append(tmp);
    //4-3
    sb.append(')');
    //4-4
    for(int j = 1; j < pos; j++) {
        if(p.charAt(j) == '(')
            sb.append(')');
        else
            sb.append('(');
    }
}
//4-5
return new String(sb.toString());

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

 

---

3. 자바 코드

class Solution {
    public String solution(String p) {
		StringBuilder sb = new StringBuilder();
		// return empty String
		String tmp = "";
		int cnt = 0,pos = 0;
		// u, v 분리
		while (true) {
			if (p.length() == 0)
				return "";
			cnt = 0;
			//첫 문자에 대한 처리
			if(p.charAt(0) == ')')
				cnt--;
			else
				cnt++;
			
			//u : 균형잡힌 괄호 문자열 만들기
			for (int i = 1; i < p.length(); i++) {
				if(p.charAt(i) ==')')
					cnt--;
				else
					cnt++;
				//균형잡힌 괄호 문자열인 경우
				if(cnt == 0) {
					pos = i;
					break;
				}
					
			}
			//u가 올바른 괄호 문자열인 경우
			if(p.charAt(0)=='(') {
				//u
				sb.append(p.substring(0, pos+1));
				//v에 대한 재귀적 수행
				tmp = solution(p.substring(pos+1,p.length()));
				sb.append(tmp);
			}
			//u가 올바른 괄호 문자열 아닌 경우
			else {
				//4-1
				sb.append('(');
				//4-2
				tmp =solution(p.substring(pos+1,p.length()));
				sb.append(tmp);
				//4-3
				sb.append(')');
				//4-4
				for(int j = 1; j < pos; j++) {
					if(p.charAt(j) == '(')
						sb.append(')');
					else
						sb.append('(');
				}
			}
			return new String(sb.toString());
		}
	}
}