재귀, 스택

프로그래머스 2020 KAKAO BLIND RECRUITMENT Level 2 문제 괄호 변환을 Java를 이용해 풀어보았다. 처음에 도저히 이 한국말이 뭔 개소리인지 알아들을 수가 없어서 다른 사람이 써둔 수도 코드를 보고 이해한 뒤에 풀기 시작했다. 못 푼 걸로 쳐야하나...

문제 링크 첨부한다.
https://programmers.co.kr/learn/courses/30/lessons/60058

---

문제 조건 이해하기

주어진 문제 조건은 다음과 같다.

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. solution(p)에 주어진 문자열 p를 처음부터 돌며 '('와 ')'의 개수가 같은 순간까지를 u로, 나머지를 v로 만들자.
2. 1에서 만든 u가 열리고 닫히는 순서가 잘 잡힌 올바른 문자열이면 다음을 수행한다. 
	2-1. u + solution(v)
3. 1에서 만든 u가 올바르지 않은 문자열이면 다음을 수행한다. 
	3-1. u의 처음과 마지막을 지우고, 남은 녀석들을 모두 반대 방향으로 뒤집는다. 편의상 reverse(u)를 수행한다고 하자.
	3-2. '(' + solution(v) + ')' + reverse(u)

일단 u와 v로 나누는 작업부터 해야한다.
이를 코드로 표현하면 다음과 같다.

String u="",v="";
int open = 0, close = 0;
for(int i=0; i<p.length(); i++){
    if(p.charAt(i)=='(') open++;
    else    close++;
    
    if(open==close){
        u = p.substring(0,i+1);
        v = p.substring(i+1);
        break;
    }
}

이 다음부터는 u가 올바른 문자열인지 아닌지에 따라 수행할 작업이 달라진다. 그렇다면 u가 올바른 문자열인지 판별해줄 메소드를 만들어보자.

---

스택을 이용해 올바른 문자 판별하기

u의 첫 문자부터 시작해서 스택에 넣어주며 다음에 들어갈 녀석이 서로 () 형태로 짝을 이루면 둘 다 날려버린다. 이 작업을 u의 끝까지 쭉 해서 마지막에 아무것도 안 남으면 올바른 문자열이고 그렇지 않으면 )(와 같이 서로 맞지 않는 쌍이 남아있을 것이다.

이를 코드로 표현하면 다음과 같다.

static Boolean isRight(String s){
        Stack<Character> stack = new Stack<>();
        for(int i=0; i<s.length(); i++){
            char cur = s.charAt(i);
            if(stack.size()==0) stack.add(cur);
            else{
                char top = stack.peek();
                if(top=='(' && cur==')')    stack.pop();
                else    stack.add(cur);
            }
        }

        return stack.size()==0 ? true : false;
    }

---

올바른 문자열 판별 후의 작업

올바른 경우에는 u + solution(v)를 반환해주면 된다.
아니면 u의 앞뒤를 한글자씩 자르고, 남은 녀석들을 반전시켜주고 문제에서 주어진 순서대로 이어붙이면 된다.

이를 코드로 표현하면 다음과 같다.

if(isRight(u)){
    answer = u + solution(v);
}
else{
     u = u.substring(1,u.length()-1);
     StringBuilder sb = new StringBuilder();
     for(int i=0; i<u.length(); i++){
          if(u.charAt(i)=='(')    sb.append(')');
          else    sb.append('(');
     }
     u = sb.toString();
     answer = "(" + solution(v) + ")" + u;
}

이제 위에서 작성한 코드들을 모두 합치면 다음과 같다. 아래는 내가 제출한 코드다.

import java.io.*;
import java.util.Stack;

public class BracketTransform {
    static String solution(String p) {
        String answer = "";
        if(p.equals("")) return answer; // 비었으면 바로 return

        String u="",v="";
        int open = 0, close = 0;
        for(int i=0; i<p.length(); i++){
            if(p.charAt(i)=='(') open++;
            else    close++;
            if(open==close){
                u = p.substring(0,i+1);
                v = p.substring(i+1);
                break;
            }
        }

        if(isRight(u)){
            answer = u + solution(v);
        }
        else{
            u = u.substring(1,u.length()-1);
            StringBuilder sb = new StringBuilder();
            for(int i=0; i<u.length(); i++){
                if(u.charAt(i)=='(')    sb.append(')');
                else    sb.append('(');
            }
            u = sb.toString();
            answer = "(" + solution(v) + ")" + u;
        }

        return answer;
    }

    static Boolean isRight(String s){
        Stack<Character> stack = new Stack<>();
        for(int i=0; i<s.length(); i++){
            char cur = s.charAt(i);
            if(stack.size()==0) stack.add(cur);
            else{
                char top = stack.peek();
                if(top=='(' && cur==')')    stack.pop();
                else    stack.add(cur);
            }
        }

        return stack.size()==0 ? true : false;
    }

    public static void main(String[] args) throws IOException {
        BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
        String p = "()))((()";
        String answer = solution(p);
        bfw.write(answer);
        bfw.close();
    }
}

오늘 배운 것

한국말은 어렵다

---

2022.03.10 재시도 ( 성공 )

저번에 풀 때 문제 설명 자체가 이해하기가 참 어렵다는 생각이 들었는데, 오늘 문제를 다시 읽어보며 이해하려 하지말고 오로지 문제가 제시하는 대로 시키는 작업만 따라간다면 이해를 못 해도 풀 수 있다는 생각이 들었다. 감정을 없애고 로봇같이 풀면 되는 것인가...

새롭게 푼 풀이 코드다.

class BracketTransform{
    static String solution(String p){
        return recursion(p);
    }

    static String recursion(String p){
        if(p.equals(""))    return "";
        StringBuilder sb = new StringBuilder();
        String v = "";

        int balance = 0;
        if(p.charAt(0)=='(')    balance++;
        else    balance--;
        sb.append(p.charAt(0));

        for(int i=1; i<p.length(); i++){
            if(p.charAt(i)=='(')    balance++;
            else    balance--;
            sb.append(p.charAt(i));

            if(balance==0) {
                if(i+1<p.length())
                    v = p.substring(i + 1);
                break;
            }
        }

        if(sb.toString().charAt(0)=='(')    return sb +recursion(v);
        else    return reverse(sb.toString(), v);
    }

    static String reverse(String u, String v){
        StringBuilder sb = new StringBuilder();
        sb.append('(');
        sb.append(recursion(v));
        sb.append(')');

        u = u.substring(1, u.length()-1);
        for(int i=0; i<u.length(); i++){
            if(u.charAt(i)=='(')    sb.append(')');
            else    sb.append('(');
        }

        return sb.toString();
    }

    public static void main(String[] args) {
        String p = ")(";
        System.out.println(solution(p));
    }
}