괄호제거-2800번(java)

https://www.acmicpc.net/problem/2800

2800번: 괄호 제거

문제

어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식의 개수를 계산하는 프로그램을 작성하시오.

이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 1+2, (3+4), (3+4*(5+6))와 같은 식은 괄호가 서로 쌍이 맞으므로 올바른 식이다.

하지만, 1+(2*3, ((2+3)*4 와 같은 식은 쌍이 맞지 않는 괄호가 있으므로 올바른 식이 아니다.

괄호를 제거할 때는, 항상 쌍이 되는 괄호끼리 제거해야 한다.

예를들어 (2+(2*2)+2)에서 괄호를 제거하면, (2+2*2+2), 2+(2*2)+2, 2+2*2+2를 만들 수 있다. 하지만, (2+2*2)+2와 2+(2*2+2)는 만들 수 없다. 그 이유는 쌍이 되지 않는 괄호를 제거했기 때문이다.

어떤 식을 여러 쌍의 괄호가 감쌀 수 있다.

입력

첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개, 많아야 10개이다. 

출력

올바른 괄호 쌍을 제거해서 나올 수 있는 서로 다른 식을 사전 순으로 출력한다.

예제 입력 1 복사

(0/(0))

예제 출력 1 복사

(0/0) 0/(0) 0/0

예제 입력 2 복사

(2+(2*2)+2)

예제 출력 2 복사

(2+2*2+2) 2+(2*2)+2 2+2*2+2

예제 입력 3 복사

(1+(2*(3+4)))

예제 출력 3 복사

(1+(2*3+4)) (1+2*(3+4)) (1+2*3+4) 1+(2*(3+4)) 1+(2*3+4) 1+2*(3+4) 1+2*3+4

코드(java)

package BaekJoon.Stack;

import java.io.*;
import java.util.*;
public class 괄호제거_2800 {
		
	static class Pair{
		
		public int x,y;
		Pair(){}
		Pair(int x, int y){
			this.x = x;
			this.y = y;
		}
		
		int getx() {return x;}
		int gety() {return y;}
	}
	public static ArrayList<Pair>arr;
	public static String str;
	
	public static HashSet<String> answer = new HashSet<String>();
	// set으로 받아야 하는 이유는 (((3)))의 경우 첫번째 두번째 세번째 괄호쌍을 지운 각각의 경우가 모두 ((3))으로 같기 때문이다.
	public static void print(int[]chk) {

		String s = new String(str);//깊은복사
		ArrayList<Integer>list = new ArrayList<>();
		//boolean tg = false;
		for(int i=0; i<chk.length; i++) {
			
			if(chk[i]==1) {
				
				int a = arr.get(i).getx();
				int b = arr.get(i).gety();
				list.add(a);
				list.add(b);				
			}
		}
		
		Collections.sort(list);
		StringBuilder ans =new StringBuilder();
		int j =0;
		for(int i=0; i<s.length(); i++) {
			if(j<list.size() && list.get(j)==i) {j++;continue;}
			ans.append(s.charAt(i));
		}
		
		answer.add(ans.toString());
	}
	
	
	public static void findAll(int[]chk, int idx ,int cnt) {
	
		if(cnt == 0) {
			print(chk);
			return;
		}

		for(int i=idx; i<arr.size(); i++) {
			
			chk[i]=1;
			findAll(chk,i+1,cnt-1);
			chk[i]=0;

		}
}
	
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader( System.in));
		str = br.readLine();
		
		Stack<Integer> st = new Stack<>();
		arr = new ArrayList<>();
		
		for(int i=0; i<str.length(); i++) {
			char c = str.charAt(i);
			if(c==')') {
				int t = st.peek();
				arr.add(new Pair(t,i));
				st.pop();
			}
			else if(c=='('){
				st.add(i);
			}
		}
		int[]chk = new int[arr.size()];
		
		
		for(int i=1; i<=arr.size(); i++) {
		findAll(chk,0,i); //combination, 여러개중 i개 선택
		}
	//	Collections.sort(answer);
		List<Integer> ls = new ArrayList(answer); // hashmap arraylist로  copy 가능
		Collections.sort(ls);
		for(int i=0; i<ls.size(); i++) {
		
			System.out.println(ls.get(i));
		}
		
	}
}

1. () 관계의 인덱스쌍을 stack을 이용하여 구한다음 ArrayList에 모두 저장한다. 

2. 조합을 이용하여 ()쌍을 제거하는 모든 경우를 구한다.