알고리즘 / [java] 2020 카카오 블라인드 테스트 / 괄호 변환

카카오 블라인드 테스트 / 괄호 변환

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

 

문제의 자세한 정보는 위의 링크에서 확인하시길 바랍니다.

알고리즘 / 2020 카카오 블라인드 테스트 / 괄호 변환

 

정리하자면 주어진 괄호를 올바른 형태로 바꾸는 문제인데 친절하게도 올바른 형태로 바꾸는 로직을 단계별로 알려주었습니다.

로직을 다시 한번 살펴보죠.

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

 

위의 로직을 하나하나 코드로 구현해보겠습니다.

 

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

class Solution {

    public String solution(String inputString) {
        if (inputString.equals("")) {
            return "";
        }
        ...

 

그리고 문제의 설명에는 나와있지 않지만 혹시나 처음부터 주어진 문자열이 올바른 괄호라면 바로 리턴해도 될 것입니다.

 

1-1. 올바른 문자열이 입력되면 바로 반환합니다.

class Solution {

    public String solution(String inputString) {
		...
        
        if (isCorrect(inputString)) {
            return inputString;
        }
        
        ...
        
    }
        
    //스택안에 주어진 괄호를 추가하면서 올바른 형태인지 확인
    public boolean isCorrect(String p) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < p.length(); i++) {
            stack.add(p.charAt(i));
            //스택안에 있는 괄호 중 짝이 맞는 괄호<'()'> 제거
            removeCorrectBracket(stack);
        }
        //스택이 비어있다면 올바른 괄호
        return stack.isEmpty();
    }

    private void removeCorrectBracket(Stack<Character> stack) {
        for (int i = 0; i < stack.size() - 1; i++) {
            if (stack.elementAt(i) == '(' & stack.elementAt(i + 1) == ')') {
                stack.removeElementAt(i + 1);
                stack.removeElementAt(i);
                removeCorrectBracket(stack);
            }
        }
    }

 

이제 본격적으로 괄호를 재배치하는 작업을 해보겠습니다.

해당 작업은 재귀를 돌릴 필요도 있으니 따로 replace 메서드로 만들어보겠습니다.

지금까지 전체적인 코드의 흐름은 이렇습니다.

    public String solution(String inputString) {
    	//정답에 들어갈 괄호를 하나씩 더해주는데 유용합니다
        StringBuilder builder = new StringBuilder();
        
        if (inputString.equals("")) {
            return "";
        }
        if (isCorrect(inputString)) {
            return inputString;
        }
        
        //재배치작업 메서드화
        replace(inputString, builder);
        ...

 

2. 문자열 w를 두 "균형 잡힌 괄호 문자열" u, v로 분리합니다.

    public List<String> splitUV(String inputString) {
        int count = 0;
        //'('가 나오면 count에 +1 ')'가 나오면 -1을 하면서 count가 다시 0이 되는 지점에서 
        //u와 v로 나눕니다
        for (int i = 0; i < inputString.length(); i++) {
            if (inputString.charAt(i) == '(') {
                count++;
            } else {
                count--;
            }

            if (count == 0) {
                return splitByIndex(inputString, i);
            }
        }
        throw new IllegalArgumentException("짝이 맞지 않습니다.");
    }

    public List<String> splitByIndex(String inputString, int i) {
        List<String> answer = new ArrayList<>();
        answer.add(inputString.substring(0, i + 1));
        answer.add(inputString.substring(i + 1));
        return answer;
    }

 

3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.

위에서 만든 splitUV를 이용하여 replace메서드에 3단계를 구현해주겠습니다.

    public void replace(String inputString, StringBuilder builder) {
        List<String> uv = splitUV(inputString);
        //u가 올바른 문자열이라면
        if (isCorrect(findU(uv))) {
        	//일단 답변에 u를 더해주고
            builder.append(findU(uv));
            //v에 대해서 다시 수행
            replace(findV(uv), builder);
        }
        ...
        
    }
        
    private String findU(List<String> uv) {
        return uv.get(0);
    }

    private String findV(List<String> uv) {
        return uv.get(1);
    }   

 

이렇게 하면 자동으로 3-1. 단계까지 완성입니다.

다음으로 조금은 까다롭게 보이는 4단계를 구현해보겠습니다.

(하지만 실제로는 그렇게 까다롭지 않습니다.)

4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.

    public void replace(String inputString, StringBuilder builder) {
        List<String> uv = splitUV(inputString);
        if (isCorrect(findU(uv))) {
            builder.append(findU(uv));
            replace(findV(uv), builder);
        } else {
        //이부분에 4단계를 구현합니다
       

4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.

builder.append("(");

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

builder.append("(");

String recursiveV = solution(findV(uv));
builder.append(recursiveV);

4-3. ')'를 다시 붙입니다.

builder.append("(");
            
String recursiveV = solution(findV(uv));
builder.append(recursiveV);
            
builder.append(")");

4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.

builder.append("(");

String recursiveV = solution(findV(uv));
builder.append(recursiveV);
builder.append(")");

builder.append(reverse(findU(uv)));


	//reverse
    private String reverse(String u) {
        StringBuilder builder = new StringBuilder();
        for (int i = 1; i < u.length() - 1; i++) {
            if (u.charAt(i) == '(') {
                builder.append(")");
            } else {
                builder.append("(");
            }
        }
        return builder.toString();
    }

 

완성입니다.

이제 생성된문자열을 builder.toString()하여 반환하면 끝입니다!

 

 전체 코드

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class Solution {

    public String solution(String inputString) {
        StringBuilder builder = new StringBuilder();

        if (inputString.equals("")) {
            return "";
        }
        if (isCorrect(inputString)) {
            return inputString;
        }
        replace(inputString, builder);
        return builder.toString();
    }

    public boolean isCorrect(String p) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < p.length(); i++) {
            stack.add(p.charAt(i));
            removeCorrectBracket(stack);
        }
        return stack.isEmpty();
    }

    private void removeCorrectBracket(Stack<Character> stack) {
        for (int i = 0; i < stack.size() - 1; i++) {
            if (stack.elementAt(i) == '(' & stack.elementAt(i + 1) == ')') {
                stack.removeElementAt(i + 1);
                stack.removeElementAt(i);
                removeCorrectBracket(stack);
            }
        }
    }

    public void replace(String inputString, StringBuilder builder) {
        List<String> uv = splitUV(inputString);
        if (isCorrect(findU(uv))) {
            builder.append(findU(uv));
            replace(findV(uv), builder);
        } else {
            builder.append("(");
            String recursiveV = solution(findV(uv));
            builder.append(recursiveV);
            builder.append(")");
            builder.append(reverse(findU(uv)));
        }
    }

    public List<String> splitUV(String inputString) {
        int count = 0;
        for (int i = 0; i < inputString.length(); i++) {
            if (inputString.charAt(i) == '(') {
                count++;
            } else {
                count--;
            }

            if (count == 0) {
                return splitByIndex(inputString, i);
            }
        }
        throw new IllegalArgumentException("짝이 맞지 않습니다.");
    }

    public List<String> splitByIndex(String inputString, int i) {
        List<String> answer = new ArrayList<>();
        answer.add(inputString.substring(0, i + 1));
        answer.add(inputString.substring(i + 1));
        return answer;
    }

    private String reverse(String u) {
        StringBuilder builder = new StringBuilder();
        for (int i = 1; i < u.length() - 1; i++) {
            if (u.charAt(i) == '(') {
                builder.append(")");
            } else {
                builder.append("(");
            }
        }
        return builder.toString();
    }

    private String findU(List<String> uv) {
        return uv.get(0);
    }

    private String findV(List<String> uv) {
        return uv.get(1);
    }
}