백준 2800 (괄호 제거) - 조합알고리즘, Stack

문제

---

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

이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 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)는 만들 수 없다. 그 이유는 쌍이 되지 않는 괄호를 제거했기 때문이다.

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

 

 

 

 

풀이

---

Stack을 이용해서 풀면 쉽게 풀 수 있는 문제였지만, 반례를 생각하지 못해서 많이 틀렸다.

 

반례를 먼저 짚고 가면,

(((0))) 일 경우, ((0)), (0), 0 이 나와야한다. 

하지만, 나는 ((0)) 이 중복되게 출력이 됐었다.

이 부분을 잘 생각해서 풀면 다른 오류는 없다.

 

괄호의 위치를 저장하는 코드다.

list = new ArrayList<location>();
for(int i = 0 ; i < me.length ; i++) {
	
	if(me[i] == '(') {
		stack.add(i);
	}
	else if(me[i] == ')') {
		int a = stack.pop();
		list.add(new location(a, i));
	}
}

location 이라는 클레스를 만들어서 한상의 괄호의 시작지점과 끝지점을 저장해 두었다.

Stack은 나중에 들어간 값이 먼저 나오므로 가장 나중에 저장된 괄호가 ')'를 만났을 때 가장 먼저 나온다.

 

그렇게 저장된 리스트를 가지고 조합알고리즘을 했다.

static void Combination(List<location> list, List<location> result, int cnt, int idx, int r) {
	
	if( r == cnt ) {
		boolean[] check = new boolean[me.length];
		for(int i = 0 ; i < result.size() ; i++) {
			check[result.get(i).a] = true;
			check[result.get(i).b] = true; 
		}
		
		StringBuilder stringBuilder = new StringBuilder();
		for(int i = 0 ; i < me.length ; i++) {
			if(!check[i]) {
				stringBuilder.append(me[i]);
			}
		}
		
		if(!set.contains(stringBuilder.toString())) {
			set.add(stringBuilder.toString());
		}
		
		return;
	}
	
	for(int i = idx ; i < list.size(); i++) {
		
		result.add(list.get(i));
		Combination(list, result, cnt, i + 1, r + 1);
		result.remove(result.size() - 1);
	}
	
	return;
}

String 으로 더해도 되지만 StringBuilder 가 String 보다 시간이 빨랐던걸로 기억해서 StringBuilder로 했다.

해당 String이 중복되는지는 HashSet<String>을 이용해서 확인했다.

 

이렇게 중복없이 String을 저장하여, 사전순으로 정렬하여 출력하면 된다.

 

<전체코드>

import java.io.*;
import java.util.*;

public class Main {	

	static StringBuilder sb = new StringBuilder();
	
	static class location{
		
		int a, b;
		
		public location(int a, int b) {
			this.a = a;
			this.b = b;
		}
	}
	
	static List<location> list;
	static List<location> result;
	static char[] me;
	static int size = 0;
	static HashSet<String> set = new HashSet<String>();
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		me = bufferedReader.readLine().toCharArray();
		
		Stack<Integer> stack = new Stack<Integer>();
		list = new ArrayList<location>();
		for(int i = 0 ; i < me.length ; i++) {
			
			if(me[i] == '(') {
				stack.add(i);
			}
			else if(me[i] == ')') {
				int a = stack.pop();
				list.add(new location(a, i));
			}
		}
		
		
		result = new ArrayList<location>();
		size = list.size();
		for(int i = 1 ; i <= size ; i++ ) {
			Combination(list, result, i, 0, 0);
		}
		
		List<String> answer = new ArrayList<String>();
		for(String string : set) {
			answer.add(string);
		}
		
		Collections.sort(answer);
		
		for(String ans : answer) {
			sb.append(ans + "\n");
		}
		System.out.println(sb);
	}
	
	
	static void Combination(List<location> list, List<location> result, int cnt, int idx, int r) {
		
		if( r == cnt ) {
			boolean[] check = new boolean[me.length];
			for(int i = 0 ; i < result.size() ; i++) {
				check[result.get(i).a] = true;
				check[result.get(i).b] = true; 
			}
			
			StringBuilder stringBuilder = new StringBuilder();
			for(int i = 0 ; i < me.length ; i++) {
				if(!check[i]) {
					stringBuilder.append(me[i]);
				}
			}
			
			if(!set.contains(stringBuilder.toString())) {
				set.add(stringBuilder.toString());
			}
			
			return;
		}
		
		for(int i = idx ; i < list.size(); i++) {
			
			result.add(list.get(i));
			Combination(list, result, cnt, i + 1, r + 1);
			result.remove(result.size() - 1);
		}
		
		return;
	}
}