괄호제거_2800번

문제

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

접근

처음에는 단순히 왼쪽 괄호가 몇 개 나오는지를 재귀함수의 파라미터로 두는 방향으로 접근했지만 생각대로 잘 풀리지 않았다. 결국 힌트를 살짝 얻었는데, 본인이 생각했던 방향과 가장 큰 차이점은 아래와 같았다.

힌트 : 괄호 짝에 맞는 번호를 사전에 저장해둔다.
본인 : 현재 '('가 몇 개 나왔는지에 대해 파라미터로 두고 매번 비교한다.

코드

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.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;

public class Main {

  static String str; // 입력 문자열
  static Set<String> set = new HashSet<>(); // 정답 셋
  static int[] pair; // 괄호 번호를 저장할 배열. 괄호가 아닌 경우 0을 저장
  static boolean[] visited; // 없앨 괄호 집합을 위한 배열. 없앨 괄호 번호라면 true

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    str = br.readLine();
    pair = new int[str.length()];
    int num = 0;
    Stack<Integer> stack = new Stack<>();

    for (int i = 0; i < str.length(); i++) {
      char c = str.charAt(i);

      if (c == '(') {
        pair[i] = ++num;
        stack.push(num);
      } else if (c == ')') {
        pair[i] = stack.pop();
      } else {
        pair[i] = 0;
      }
    }

    visited = new boolean[num + 1];
    func(1);

    List<String> list = new ArrayList<>(set);
    Collections.sort(list);

    for (String ans : list) {
      if (!ans.equals(str)) {
        bw.write(ans + '\n');
      }
    }

    bw.flush();
    bw.close();
    br.close();
  }

  static void func(int idx) {
    if (idx == visited.length) {
      StringBuilder sb = new StringBuilder();
      for (int i = 0; i < str.length(); i++) {
        if (!visited[pair[i]]) {
          // 없앨 문자가 아니라면 문자열을 이어붙인다.
          sb.append(str.charAt(i));
        }
      }

      String tmpStr = sb.toString();
      if (set.isEmpty() || !set.contains(tmpStr)) {
        set.add(tmpStr);
      }
      return;
    }

    for (int i = idx; i < visited.length; i++) {
      visited[i] = true;
      func(i + 1);
      visited[i] = false;
      func(i + 1);
    }
  }
}