[BOJ] 백준 2800번 괄호 제거 (Java)

#2800 괄호 제거

난이도 : 골드 5

유형 : 문자열 / 조합

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개이다. 

▸ 출력

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

 

문제 풀이  

문자열 조합을 구하는 문제이다. 분기 조건은 괄호를 제거하냐 안하냐 두 가지이다. 그러려면 먼저 괄호의 쌍을 구해준 다음 괄호의 갯수만큼 재귀를 돌려 모든 경우의 수를 구해주면 된다.

 

괄호의 쌍 구하기

 '('에 대한 정보를 저장하고 ')'가 나오면 가장 늦게 들어간 '('를 꺼내어 쌍을 맞추면 되므로 stack을 사용해주면 된다.

Stack<Integer> s = new Stack<>();
for(int i=0; i<line.length(); i++) {
    char c = line.charAt(i);
    if(c == '(') {
        s.push(i);
    }else if(c == ')'){
        brackets.add(new int[] {s.pop(), i});
    }
}

 

괄호 존재여부 모든 조합 구하기

괄호 쌍의 갯수만큼 조합을 돌려서 각 괄호가 존재하냐 안하냐 조합을 구해주면 된다. 최대 괄호의 쌍은 10개이므로 최대 2^10의 경우의 수가 나올 수 있다. 

• 괄호의 쌍을 뺀 조합은 true로 처리해서 문자열에서 해당 부분만 제거한 후 문자열을 다시 저장한다.
• 만약 모든 괄호의 쌍이 포함되어 있다면 주어진 문자열 그대로인 것과 같으므로 이는 제외한다.

 

풀이 코드 

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

public class Main {

	static List<int[]> brackets;
	static Set<String> result;
	static boolean[] check;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = br.readLine();
		
		brackets = new ArrayList<>();
		Stack<Integer> s = new Stack<>();
		for(int i=0; i<line.length(); i++) {
			char c = line.charAt(i);
			if(c == '(') {
				s.push(i);
			}else if(c == ')'){
				brackets.add(new int[] {s.pop(), i});
			}
		}
		
		check = new boolean[line.length()];
		result = new TreeSet<>();
		comb(0, line.toCharArray());
		
		result.stream().forEach(System.out::println);
	}
	
	static void comb(int depth, char[] str) {
		if(depth == brackets.size()) {
			boolean f = false;
			StringBuilder sb = new StringBuilder();
			for(int i=0; i<str.length; i++) {
				if(!check[i]) {
					sb.append(str[i]);
				} else f = true;
			}
			if(f) {
				result.add(sb.toString());
			}
			return;
		}
		
		comb(depth+1, str);
		
		int[] bracket = brackets.get(depth);
		check[bracket[0]] = true;
		check[bracket[1]] = true;
		comb(depth+1, str);
		check[bracket[0]] = false;
		check[bracket[1]] = false;
	}
}