[프로그래머스] 괄호 변환 - 2020 KAKAO BLIND RECRUITMENT (Java) / 구현 / 스택

문제

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

풀이

import java.util.*;

class Solution { 
    public String solution(String p) {
        String answer = "";
        answer += convert(p);
        return answer;
    }
    
    private String convert(String p) {
        if(p.equals("")) return "";
        
        int i;
        int left = 0;
        int right = 0;
        for(i=0; i< p.length(); i++) {
            if(p.charAt(i) == '(') left++;
            if(p.charAt(i) == ')') right++;
            if(left == right) break;
        }
        
        String u = p.substring(0, i+1);
        String v = p.substring(i+1, p.length());
        
        String temp = "";
        if(isAlright(u)) {
            return u + convert(v);
        } else {
            temp += "(";
            temp += convert(v);
            temp += ")";
            if(u.length() > 0) {
                u = u.substring(1, u.length() -1);
            }
            for(i=0; i< u.length(); i++) {
                temp += u.charAt(i) == '(' ? ')' : '(';
            }
        }
        return temp;
    }
    
    private boolean isAlright(String u) {
        Stack<Character> stack = new Stack<>();
        for(int i=0; i< u.length(); i++) {
            if(u.charAt(i) == '(') {
                stack.push(u.charAt(i));
            } else {
                if(stack.isEmpty()) return false;
                stack.pop();
            }
        }
        return stack.isEmpty() ? true : false;
    }
}

위 방식과 동일하게 코드를 작성하면 된다.

4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.

"재귀적으로 수행" 해야하기 때문에 함수로 위 과정을 작성해야한다.

• p를 하나씩 보면서 최소 길이의 균형잡힌 문자열을 만족하면 (  left == right )
  • 이를 u라고 한다. ( String u = p.substring(0, i+1) )
  • 나머지를 v라고 한다. ( String v = p.substring(i+1, p.length()) )
• u가 올바른 문자열 (isAlright 함수, 아래에 설명!) 이면
  • u와, 나머지 v에 대해 재귀적으로 수행( convert(v) ) 한 값을 더해서 ( + ) 반환( return ) 한다.

return u + convert(v);

• 올바른 문자열이 아니라면

temp += "("; // 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
temp += convert(v); // 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
temp += ")"; // 4-3. ')'를 다시 붙입니다.
if(u.length() > 0) { 
	u = u.substring(1, u.length() -1); // 4-4. u의 첫 번째와 마지막 문자를 제거하고,
}
for(i=0; i< u.length(); i++) { // 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
	temp += u.charAt(i) == '(' ? ')' : '(';
}

• 생성된 문자열을 반환합니다.

return temp;

 

isAlright 함수

: 올바른 괄호 문자열인지 확인하는 함수

private boolean isAlright(String u) {
        Stack<Character> stack = new Stack<>();
        for(int i=0; i< u.length(); i++) {
            if(u.charAt(i) == '(') {
                stack.push(u.charAt(i));
            } else {
                if(stack.isEmpty()) return false; 
                stack.pop();
            }
        }
        return stack.isEmpty() ? true : false;
    }

스택(선입 후출)에

• '(' 인 경우 삽입한다.
• ')' 인 경우 스택에 있는 '(' 를 pop한다.
  • 이때, 스택이 비어있다면 ')'의 짝이 없다는 의미이므로 false를 반환한다.

위 과정을 String의 길이만큼 수행했을 때

• 스택이 비어있지 않다면 스택에 남아있는 '('의 짝이 없다는 것을 의미하므로 false를 반환한다.
• 스택이 비어있다면 모든 괄호가 짝을 찾은 것(올바른 괄호 문자열)이므로 true를 반환한다.