괄호 제거

문제 설명

수식이 주어지는데, 괄호를 제거해서 나올 수 있는 경우를 모두 출력하는 문제이다.

• 수식은 올바른 형태로만 입력이 들어온다.
• 예를들어 (2+(22)+2)에서 괄호를 제거하면, (2+22+2), 2+(22)+2, 2+22+2를 만들 수 있다.
  • 하지만, (2+22)+2와 2+(22+2)는 만들 수 없다. (부적적한 수식이기 때문)

아이디어

괄호 쌍을 하나의 묶음으로 보고 조합을 이용한다.

조합에서 나온 경우의수가 한 묶음이므로 묵음에 있는 괄호 좌표를 출력할 것인지 안할 것인지 판단하고 정답 문자열에 넣어준다.

풀이

	static Set<List<Integer>> noPicks = new HashSet<>();
	static List<int[]> results;
	static String[] inputs;
	static TreeSet<String> answers;

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

		inputs = reader.readLine().split("");
		// 괄호 쌍 위치들(괄호 여는 위치, 괄호 닫는 위치)
		results = new ArrayList<>();
		Stack<Integer> s = new Stack<>();
		for (int i = 0; i < inputs.length; i++) {
			String input = inputs[i];
			if (input.equals("(")) {
				s.push(i);
			} else if (input.equals(")")) {
				if (!s.isEmpty()) {
					results.add(new int[] {s.pop(), i});
				}
			}
		}
		comb(0, 0, new ArrayList<>());

		answers = new TreeSet<>();
		for (List<Integer> noPick : noPicks) { // nopicks는 안뽑아야 하는 results 위치
			Set<Integer> set = noPick.stream().map(idx -> results.get(idx))
				.map(ints -> new Integer[] {ints[0], ints[1]})
				.flatMap(Arrays::stream)
				.collect(Collectors.toSet());

			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < inputs.length; i++) {
				if (set.contains(i)) {
					continue;
				}
				sb.append(inputs[i]);
			}

			if (sb.length() == inputs.length)
				continue;

			answers.add(sb.toString());
		}

		answers.forEach(System.out::println);
	}