[LeetCode] 1021. Remove Outermost Parentheses

https://leetcode.com/problems/remove-outermost-parentheses/

Remove Outermost Parentheses - LeetCode

 

A valid parentheses string is either empty (""), "(" + A + ")", or A + B, where A and B are valid parentheses strings, and + represents string concatenation.  For example, "", "()", "(())()", and "(()(()))" are all valid parentheses strings.

A valid parentheses string S is primitive if it is nonempty, and there does not exist a way to split it into S = A+B, with A and B nonempty valid parentheses strings.

Given a valid parentheses string S, consider its primitive decomposition: S = P_1 + P_2 + ... + P_k, where P_iare primitive valid parentheses strings.

Return S after removing the outermost parentheses of every primitive string in the primitive decomposition of S.

 

해석

올바른 괄호 문자열은 빈 ( ""), "("+ A + ") 또는 A + B입니다. 여기서 A와 B는 유효한 괄호 문자열이고 +는 문자열 연결을 나타냅니다. 예를 들어, "", "()", "(())()" 및"(()(()))"는 모두 유효한 괄호 문자열입니다.

유효한 괄호 문자열 S는 비어 있지 않은 경우 프리미티브이며 A와 B가 비어 있지 않은 유효한 괄호 문자열을 사용하여 S = A + B로 분할하는 방법이 없습니다.

유효한 괄호 문자열 S가 주어지면, 그 원시 분해를 고려하십시오. S = P_1 + P_2 + ... + P_k, 여기서 P_i는 원시 유효 괄호 문자열입니다.

S의 원시 분해에서 모든 원시 문자열의 가장 바깥 쪽 괄호를 제거한 다음 S를 반환합니다.

 

Example 1.

Input: "(()())(())" Output: "()()()"

Example 2.

Input: "(()())(())(()(()))" Output: "()()()()(())"

 

기본지식

StringBuilder

• 문자열에 문자 혹은 문자열을 추가할 때 String + String 보다 성능이 뛰어나다.
• 하드러너 - '자바 StringBuilder 사용법 및 사용하느 이유 글' 참고 https://hardlearner.tistory.com/288

 

문제 해석

 

예제 해석에 앞서 문제에 대해 이해하고 넘어가자

입력되는 문자열 S는 빈 문자열 "" 이거나 소괄호(parenthesis)로 이루어진 프리미티브 타입 문자열 이다.

문자열 S는 원시괄호의 합으로 이루어져 있다.

원시괄호란 열림괄호 '(' 로 시작해  닫힘괄호 ')' 로 끝나면서 각각 기호의 개수가 동일한 하나의 쌍을 의미한다.

* "()" 은 열림괄호 1개 닫힘괄호 1개로 이루어진 원시괄호이며, "(()())" 은 열림괄호 3개 닫힘괄호 3개로 이루어진 원시괄호다 *

예를 들어 S = "()(())" 의 경우,  첫번째 원시괄고 "()", 두번째 원시괄호 "(())"  총 2개의 원시괄호의 합으로 이루어져있다.

이를 S = A + B 로 표현 할 수 있고 A와 B는 각 원시괄호를 나타낸다

즉, S = "()(())" 에서 A = "()" / B = "(())" / S = "()" + "(())" 로 표현 할 수 있다. 

 

문제에서는 각 원시괄호의 가장 바깥쪽 괄호를 제거 한 문자열 S를 반환할 것을 요구하고 있다.

 즉, S = "()(())" /  S = "()" + "(())" 에서 원시괄호 "()" , "(())" 의 가장 바깥쪽 괄호를 제거한 모습은 S = ""+ "()" / S = "()" 이다.

 

예제 해석

Example 1.

S = "(()())(())" 

S = "(()())" + "(())"

가장 바깥쪽 괄호 제거 후. S = "()()" + "()"

Output : "()()()"

 

Example 2.

S = "(()())(())(()(()))" 

S = "(()())" + "(())" + "(()((()))"

가장 바깥쪽 괄호 제거 후. S = "()()" + "()" + "()(())"

Output : "()()()()(())"

 

솔루션 Solution

class Solution {
    public String removeOuterParentheses(String S) {        
        
        // Output 생성에 빌더를 사용한다.
        StringBuilder builder = new StringBuilder();
        
        // 열림괄호'(' 의 개수를 카운트 한다
        // 원시괄호 시작과 끝을 알기 위함이다
        int openerCount = 0;
        
        for(char c : S.toCharArray()){
        	
            // 열림괄호며 카운트가 0인 경우는 원시괄호의 시작점이다.
            if(c == '(' && openerCount == 0){
            	// 열림 괄호 카운트를 증가시킨다
                // 원시괄호의 가장 바깥의 괄호는 삭제 되기때문에 output 빌더에 추가하지않는다
                openerCount++;
            
            // 열림괄호며 카운트가 0 이상인 경우는 원시괄호의 내부의 열림 괄호
            }else if (c == '(' && openerCount > 0){
            
            	// 열림 괄호 카운트를 증가시킨다
                openerCount++;
                // 원시괄호의 내부 괄호이기 때문에 output 빌더에 추가한다.
                builder.append(c);
            
            // 닫힘괄호며 카운트가 0이상인 경우는 
            // 원시괄호의 내부 닫힘 괄호이거나 원시괄호의 끝점이다.
            }else if (c == ')'){
            	
                // 열림괄호 카운트를 감소시켜 괄호쌍을 맞춘다.
                openerCount --;
                
                // 열림괄호의 카운트가 0이 아닌경우는
                // 괄호쌍이 맞춰지지 않은 상태 즉, 원시괄호가 완성되지 않은 상태이다.
                // 원시괄호의 내부 닫힘 괄호이기 때문에 output 빌더에 추가한다.
                if(openerCount != 0) builder.append(c);
               	
                // openerCount == 0 인 경우는 원시괄호가 완성된 상태로
                // 원시괄호의 가장 바깥의 괄호는 삭제 되기때문에 output 빌더에 추가하지않는다
            }
        }
        
        //문자열 S에서 원시괄호의 가장 바깥 괄호가 삭제된 문자열을 반환한다.
        return builder.toString();
    }
}

 

원시괄호를 알아내는 방법

• 원시괄호는 열림괄호로 시작해 닫힘괄호 끝나면서 두개의 개수가 서로 동일하게 짝을 이루는 괄호쌍을 뜻한다.
• 열림괄호 로 시작하는 지점부터 열림괄호 개수를 카운트하고 닫힘 괄호가 나올때마다 괄호 쌍을 이뤘다는 의미로 카운트 하나를 내린다.
•  닫힘괄호가 나와 열림괄호 개수 카운트를 내렸는데 그 숫자가 0이 될 때, 모든 괄호가 쌍을 이룬 것이고 이 지점이 원시괄호의 끝 지점이다.

해당 조건을 if문으로 표시하면 아래와 같다

int openerCount = 0;

if( c == '(' && openerCount == 0){
	// 원시괄호 시작점
    openerCount++;
    
}else if ( c == '(' && openerCount > 0){
	//원시괄호 내부
    openerCount++;
}else if (c == ')'){
	
    //괄호쌍을 이루어 졌기때문에 카운트다운
    openerCount--
    
    if(openerCount == 0){
    	// 모든 괄호쌍 완성
    	// 원시괄호 끝점
    }
}

 

원시괄호의 합으로 이루어진 S에서 원시괄호를 분리할 방법을 알아냈다.

이제 각 원시괄호에서 가장 바깥 괄호를 제거할 방법을 알아보자.

 

우리는 열림괄호 카운트 개수를 이용해 각 원시괄호의 시작과 끝점을 알아 낼 수 있었다.

문제에서는 원시괄호의 가장 바깥 괄호를 제외한 나머지를 요구하고 있다.

즉, 우리는 문자열 S의 문자를 하나씩 탐색하며 해당 문자가 원시괄호의 시작점 혹은 끝점인지 판단하고, 반환할 문자열에서 제외 시키면 된다.

반환 문자열 생성에는 StringBuilder를 사용하며 문자열 S를 탐색하며 한문자씩 append 하고, 최종 결과물을 반환하며 마무리한다.

 

이 문제는 사실 풀이에 큰 어려움이 없으나 문제 자체를 이해하기 까지 긴 시간이 걸릴 수 있는 문제였다.