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

작성일: 2024-11-22

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

접근 방식

문제에서 주어진 “올바른 괄호 문자열” 변환 알고리즘을 순서대로 구현했다.

잘못된 접근

import java.util.*;

class Solution {
    public String solution(String p) {
        return recur(p);
    }

    // 두 문자열을 '균형잡힌 괄호 문자열'인지 확인
    boolean sep(String u, String v){
        int left=0, right=0;
        int left2=0, right2=0;
        for(char t:u.toCharArray()){
            if(t=='(') left++;
            else right++;
        }
        for(char t:v.toCharArray()){
            if(t=='(') left2++;
            else right2++;
        }

        return (left==right) && (left2==right2);
    }

    // 재귀 함수
    String recur(String p){
        if(p.length()==0) return ""; // 빈 문자열 반환
        String u = "";
        String v = "";
        for(int i=1; i<=p.length(); i++){
            // 균형잡힌 괄호 문자열로 분리
            if(sep(p.substring(0, i), p.substring(i, p.length()))){
                u = p.substring(0, i);
                v = p.substring(i, p.length());
                break;
            }
        }
        boolean flag = isValid(u);
        // u가 올바른 괄호 문자열이라면
        if(flag){
            return u + recur(v);
        }
        // 그렇지 않다면
        else{
            StringBuilder sb = new StringBuilder();
            for(int i=1; i<u.length()-1; i++) sb.append(u.charAt(i));
            return "(" + recur(v) + ")" + sb.reverse();
        }
    }

    // '올바른 괄호 문자열' 여부 확인 함수
    boolean isValid(String u){
        Stack<Character> stack = new Stack<>();
        int left = 0, right = 0;
        for(char t:u.toCharArray()){
            if(t=='(') left++;
            else right++;
        }
        if(left!=right) return false;

        for(char t:u.toCharArray()){
            if(t=='(') stack.push('(');
            else{
                if(stack.isEmpty()) return false;
                else stack.pop();
            }
        }

        return true;
    }
}

주어진 세 개의 테스트케이스를 통과해서 제출했지만, 정확성 테스트에서 테스트 12 ~ 테스트23은 모두 실패라는 결과가 나왔다.

다시 꼼꼼히 살펴보다 큰 실수를 발견했다. 문자열의 괄호 방향을 뒤집어서 뒤에 붙여야하는 4-4 로직에서, 괄호를 뒤집는게 아니라, 문자열 전체를 뒤집어서 통과하지 못했던 것.

변환 전

StringBuilder sb = new StringBuilder();
for(int i=1; i<u.length()-1; i++) sb.append(u.charAt(i));
return "(" + recur(v) + ")" + sb.reverse();

변환 후

StringBuilder sb = new StringBuilder();
for(int i=1; i<u.length()-1; i++) {
    if(u.charAt(i)=='('){
        sb.append(')');
    }else{
        sb.append('(');
    }
}
return "(" + recur(v) + ")" + sb;

결과

소스 코드

import java.util.*;

class Solution {
    public String solution(String p) {
        return recur(p);
    }

    // 두 문자열이 '균형잡힌 괄호 문자열'인지 확인
    boolean sep(String u, String v){
        int left=0, right=0;
        int left2=0, right2=0;
        for(char t:u.toCharArray()){
            if(t=='(') left++;
            else right++;
        }
        for(char t:v.toCharArray()){
            if(t=='(') left2++;
            else right2++;
        }

        return (left==right) && (left2==right2);
    }

    // 재귀 함수
    String recur(String p){
        if(p.length()==0) return ""; // 빈 문자열 반환
        String u = "";
        String v = "";
        for(int i=1; i<=p.length(); i++){
            // 균형잡힌 괄호 문자열로 분리
            if(sep(p.substring(0, i), p.substring(i, p.length()))){
                u = p.substring(0, i);
                v = p.substring(i, p.length());
                break;
            }
        }
        boolean flag = isValid(u);
        // u가 올바른 괄호 문자열이라면
        if(flag){
            return u + recur(v);
        }
        // 그렇지 않다면
        else{
            StringBuilder sb = new StringBuilder();
            for(int i=1; i<u.length()-1; i++) {
                if(u.charAt(i)=='('){
                    sb.append(')');
                }else{
                    sb.append('(');
                }
            }
            return "(" + recur(v) + ")" + sb;
        }
    }

    // '올바른 괄호 문자열' 여부 확인 함수
    boolean isValid(String u){
        Stack<Character> stack = new Stack<>();
        for(char t:u.toCharArray()){
            if(t=='(') stack.push('(');
            else{
                if(stack.isEmpty()) return false;
                else stack.pop();
            }
        }
        return stack.isEmpty() ? true : false;
    }
}

느낀 점

구현 문제는 정신을 똑바로 차리고, 주어진 문제를 이해하고 그대로 구현하는 능력이 중요하다.😀😀