[백준 2800, Java] 괄호제거

문제

www.acmicpc.net/problem/2800

2800번: 괄호 제거

 

풀이

1) 괄호가 쌍을 이루기 때문에 우선 괄호 쌍의 인덱스를 찾는다. 

- (0/(0)) 의 경우 인덱스0 과 인덱스 6가 쌍을 이루고, 인덱스 3과 인덱스 5이 쌍을 이룬다.

- 괄호 쌍의 위치를 저장하기 위해 Pair 클래스를 만들고 이를 ArrayList<Pair> pairs에 저장한다. 

 

       //수식문자열을 char 리스트로 받기
       originalExpression = br.readLine().trim();
        expression = new char[originalExpression.length()];
        for(int index = 0 ;index<originalExpression.length(); index++){
            expression[index] = originalExpression.charAt(index);
        }

        //괄호쌍의 인덱스를 찾기
        pairs = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        for(int index = 0 ; index<expression.length; index++){
            char currentChar = expression[index];
            if(currentChar =='('){
                stack.push(index);
            }
            else if(currentChar==')'){
                Pair pair = new Pair(stack.pop(),index);
                pairs.add(pair);
            }
        }

 

2) pairs를 순회하면서 pairs의 "해당 인덱스를 삭제한다/삭제하지 않는다"를 구현한다.

- 이를 위해 입력받은 문자열을 char[] expression 로 입력받는다. 

- pairs의 index 0 은 (0,6)이다  expression에서 인덱스 0, 인덱스 6을 ' '으로 바꾼다.

- "삭제하지 않는다" 를 구현할 때는 expression에서 인덱스 0, 인덱스 6을 각각 ' (', ')'으로 바꾼다.

- 이때 삭제/삭제안함 처리된 expression은 HashSet에 담아야 중복제거가 된다. 

public static void removePair(int index, char[] expression){
        if(index>=N){
            String removeExpression = new String(expression);
            removeExpression=removeExpression.replaceAll(" ", "");
            removedExpressions.add(removeExpression);
        }
        else{
            Pair currentPair= pairs.get(index);

            //currentPair삭제
            expression[currentPair.leftIndex] = ' ';
            expression[currentPair.rightIndex]= ' ';
            removePair(index+1, expression);

            // currentPair삭제안함
            expression[currentPair.leftIndex] = '(';
            expression[currentPair.rightIndex]= ')';
            removePair(index+1, expression);

        }
    }

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
    public static class Pair{
        int leftIndex;
        int rightIndex;

        Pair(int leftIndex, int rightIndex){
            this.leftIndex = leftIndex;
            this.rightIndex = rightIndex;
        }
    }
    public static ArrayList<Pair> pairs;     // 괄호 쌍 인덱스 리스트
    public static int N;                    // 괄호 쌍의 갯수
    public static char[] expression;
    public static String originalExpression;
    public static HashSet<String> removedExpressions;

    public static void main(String[] args) throws Exception{
        BufferedReader  br  = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        //수식문자열을 char 리스트로 받기
        String originalExpression = br.readLine().trim();
        expression = new char[originalExpression.length()];
        for(int index = 0 ;index<originalExpression.length(); index++){
            expression[index] = originalExpression.charAt(index);
        }

        //괄호쌍의 인덱스를 찾기
        pairs = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        for(int index = 0 ; index<expression.length; index++){
            char currentChar = expression[index];
            if(currentChar =='('){
                stack.push(index);
            }
            else if(currentChar==')'){
                Pair pair = new Pair(stack.pop(),index);
                pairs.add(pair);
            }
        }

        removedExpressions = new HashSet<>();           //  괄호가 제거된 수식
        N = pairs.size();                               // 괄호쌍의 갯

        removePair(0,expression);

        List removedExpressionList = new ArrayList(removedExpressions);
        Collections.sort(removedExpressionList);

        for(int index = 0; index<removedExpressionList.size(); index++){
            if(!removedExpressionList.get(index).equals(originalExpression)){
                bw.write(removedExpressionList.get(index)+"\n");
            }
        }

        bw.flush();

    }
    public static void removePair(int index, char[] expression){
        if(index>=N){
            String removeExpression = new String(expression);
            removeExpression=removeExpression.replaceAll(" ", "");
            removedExpressions.add(removeExpression);
        }
        else{
            Pair currentPair= pairs.get(index);

            //currentPair삭제
            expression[currentPair.leftIndex] = ' ';
            expression[currentPair.rightIndex]= ' ';
            removePair(index+1, expression);

            // currentPair삭제안함
            expression[currentPair.leftIndex] = '(';
            expression[currentPair.rightIndex]= ')';
            removePair(index+1, expression);




        }
    }
}