[BaekJoon] 2800 괄호 제거 (Java)

1.  문제 링크

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

2.  문제

요약

• 괄호가 서로 쌍이 맞게 쳐져 있는 수식을 올바른 식이라고 부릅니다.
• 올바른 식에서 괄호를 제거할 때, 항상 쌍이 되는 괄호끼리 제거해야 합니다.
• 예를 들어, (2 + (2 2) + 2)에서 괄호를 제거할 때는 (2 + 2 2 + 2)는 가능하지만 (2 + 2 * 2) + 2은 쌍이 되지 않는 괄호를 제거했기 때문에 불가능합니다.
• 어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식들을 구하는 문제입니다.
• 입력: 첫 번째 줄에 음이 아닌 정수로 이루어진, 괄호가 올바르게 쳐져있는 수식이 주어집니다.
  • 숫자, '+', '-', '*', '/', '(', ')'로만 이루어져 있고 수식의 최대 길이는 200이며 괄호쌍은 적어도 1개, 많으면 10개까지 존재합니다.
• 출력: 올바른 괄호쌍을 제거해서 나올 수 있는 서로 다른 식을 사전순으로 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;
import java.util.TreeSet;

public class Main {
	static char[] expression;
	static ArrayList<bracket> brackets;
	static TreeSet<String> set = new TreeSet<>();
	boolean[] visited;
	boolean isFirst = true;
	public void findExpressions(int d) {
		if(d == brackets.size()) {
			if(isFirst) {
				isFirst = false;
			} else {
				StringBuilder sb = new StringBuilder();
				for(int i = 0; i < expression.length; i++) {
					if(visited[i]) {
						sb.append(expression[i]);
					}
				}
				set.add(sb.toString());
			}
			return;
		}
		bracket b = brackets.get(d);
		visited[b.start] = true;
		visited[b.end] = true;
		findExpressions(d + 1);
		visited[b.start] = false;
		visited[b.end] = false;
		findExpressions(d + 1);
	}
	
	public void getAllExpressions() {
		visited = new boolean[expression.length];
		Arrays.fill(visited, true);
		findExpressions(0);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		Stack<Integer> bracket_loc = new Stack<Integer>();
		brackets = new ArrayList<bracket>();
		expression = br.readLine().toCharArray();
		br.close();
		for(int i = 0; i < expression.length; i++) {
			if(expression[i] == '(') {
				bracket_loc.push(i);
			} else if(expression[i] == ')') {
				brackets.add(new bracket(bracket_loc.pop(), i));
			}
		}
		StringBuilder sb = new StringBuilder();
		Main m = new Main();
		m.getAllExpressions();
		for(String s : set) {
			sb.append(s).append('\n');
		}
		bw.write(sb + "\n");
		bw.flush();
		bw.close();
	}
	
	public static class bracket {
		int start, end;
		public bracket(int start, int end) {
			this.start = start;
			this.end = end;
		}
	}
}

4.  접근

• 주어진 수식에서 괄호쌍을 표시하기 위해 괄호쌍의 시작 인덱스와 끝 인덱스를 가지는 bracket 클래스를 생성합니다.
• 주어진 수식에서 괄호의 시작인 '('가 나오는 index들을 스택에 넣어주고 괄호의 끝인 ')'가 나올 때마다 스택에서 하나씩 index를 꺼내서 ')'와 쌍을 이루도록 합니다. 이 쌍을 bracket 객체를 이용해서 나타내고 이를 ArrayList에 하나씩 넣어줍니다.
• 재귀를 통해 괄호들을 제거해주고 이를 TreeSet에 넣어줍니다. TreeSet은 기본적으로 객체를 오름차순으로 정렬해주기 때문에 최종적으로 TreeSet에 있는 수식들을 순서대로 출력합니다.