깔끔한 코드와 재귀로 프로그래머스 괄호변환 문제를 해석하고 풀이합니다.

프로그래머스 - 괄호변환

문제바로가기

문제유형

Stack

문제 설명

괄호를 확인하여 올바른 열고닫음의 짝수 괄호인지 확인하고 열고닫임이 맞지 않는 경우 변환하여 리턴하는 문제

stack을 이용한 괄호 문제를 어렵게 내기 위해 꼬아 놓은 듯한 문제라 문제를 이해하는 것이 쉬운 편은 아님

괄호를 설명하는 예시

1. (()())() => 괄호가 짝도 맞고 열고 닫음 도 맞다 그대로 리턴
2. )(       => 괄호가 짝은 맞지만 열고닫음이 틀리다 => ()로 변환하여 리턴
3. ()))((() => 괄호가 짝은 맞지만 열고닫음이 틀리다 => ()(())()로 변환하여 리턴

풀이법

문제 지면에 자세한 알고리즘이 설명되어 있다 사실 이것을 잘 이해하는 것이 중요하다.

일반적인 Stack을 이용한 괄호 판별문제

1. ”(“ 열린 괄호를 스택에 넣다가 “)” 닫힌 괄호가 나오면 스택에서 꺼낸다.
2. 1번 작업을 모두 완료 후 스택이 최종적으로 비었으면 짝이 맞다는 것으로 올바른 괄호로 판단하는 것이 기본 알고리즘

문제를 해결하는 핵심

올바른 여닫음 및 쌍으로 이루진 괄호를 판단하는 기준이 문제 해결의 핵심이다 그리고 괄호를 나누고 재조합하는 단위 U, V의 정의를 자세히 보아야한다.

U의 정의

괄호가 “)(“, “))((“ 열고닫음이 반대인 경우라도 서로 짝이 맞으면 U가 된다.
그리고 최소한의 단위여야한다 (())(()) 경우 짝이 맞지만 (()), (()) 쪼개 지기 때문에 최소 개수로 짝이 맞으면 U가 된다.

V의 정의

V는 U를 분리한 나머지괄호를 의미한다.

주어진 괄호 ()))((()에 대해서 처리를 순서대로 본다면 
1. ()))((() => U = (),   V = ))((() 
   => U "()" 개수도 짝이며 열고닫음도 맞다 
   => U +  재귀(V) 합친후 리턴한다
2. ))((()   => U = ))((, V = ()
   => U "))((" 개수는 짝이지만 열고닫음이 맞지 않다. 변환 처리를 한다
   => "(" + 재귀(V) +")" + 변환처리(U) 를 반환 한다.

• U가 열고 닫음이 바르면 U+재귀(V) 리턴하고
• U가 열고 닫음이 틀리면 "("+재귀(V)+")"+ 변환처리(U) 리턴한다

U를 판단하고 분리하는 조건

U를 판단하는 메소드는 stack을 이용해서 괄호를 판단하는 로직을 구성한다

1. ”(“ 스택에 넣는다, 여는괄호 개수 증가
2. ”)” 스택에서 뺀다 닫는괄호 개수 증가
3. for loop를 수행하는 동안 매번 여는괄호 == 닫는괄호 체크하여 같으면 loop를 종료한다
4. 스택이 비었으면 열고닫음이 맞는 괄호 이므로 TRUE를 리턴 아니면 FALSE를 리턴한다.
5. 이때 까지 수행한 괄호 문자열의 INDEX 저장하여 추후 U,V를 분리해 내는 기준 INDEX로 활용한다.

올바르지 않는 괄호의 변환처리의 조건

1. ”))(( “ U가 열고 닫음이 틀리면
2. 첫번째와 마지막을 제거하여 “)(“만 남게 된다.
3. ”)(“ => 뒤집은 후 () 리턴한다

중요! - U가 “)(“인 경우는 => 첫번째와 마지막을 제거 => “” 공백을 리턴한다.

문제 처리의 골격

올바른괄호여부 = 괄호체크(괄호)  
 
if (올바른괄호여부 == 참)
   return U + 재귀함수(V)
else
   return "("+재귀함수(V)+")" + 변환처리(U)

소스코드

public class Solution {
    private static int index = 0;

    public static String solution(String p) {
        if (p.equals("")) return "";
        boolean check = check(p);
        String U = p.substring(0, index), V = p.substring(index);
        return check ? U + solution(V) : "(" + solution(V)+ ")" + reverse(U);
    }

    // U를 판단하는 메소드
    private static boolean check(String str) {
        Stack<Character> stack = new Stack<>();
        int balanced = 0;
        index = 0;

        for (char ch : str.toCharArray()) {
            index++;
            if ('(' == ch) {
                stack.push(ch);balanced++;
            } else {
                if (!stack.isEmpty()) stack.pop();balanced--;
            }

            if (balanced == 0) break;
        }

        return stack.isEmpty();
    }

    // 올바르지 않은 괄호를 변환하는 메소드
    private static String reverse(String str) {
        return str.substring(1, str.length() - 1)
                .chars()
                .mapToObj(v -> '(' == v ? ")" : "(")
                .collect(Collectors.joining(""));
    }
}