문제
수식에서 괄호 쌍을 하나 이상 제거하여 만들 수 있는 서로 다른 수식을 사전순으로 출력하라. 원래 수식은 제외한다.
입력
괄호가 올바르게 짝지어진 수식이 주어진다 (길이 최대 200).
출력
괄호 제거로 만들 수 있는 서로 다른 수식을 사전순으로 출력한다.
예제
| 입력 | 출력 |
|---|---|
(0/(0)) | (0/0) 0/(0) 0/0 |
풀이
스택으로 괄호 쌍을 매칭하고, 재귀로 모든 제거 조합을 시도하여 TreeSet으로 중복을 제거한다.
- 스택을 이용해
(와)쌍의 인덱스를 매칭한다 - 각 괄호 쌍에 대해 제거/유지를 선택하는 조합을 재귀로 탐색한다
- 하나 이상 제거된 경우만
TreeSet에 추가하여 중복 제거와 사전순 정렬을 동시에 처리한다
핵심 아이디어: 괄호 쌍이 최대 10개이므로 2^10 = 1024가지 조합을 전수 탐색해도 충분하다.
코드
package day749;
import java.util.*;
import java.io.*;
public class Day726BOJ2800괄호제거 {
static char[] ch;
static Stack<Integer> st;
static List<int[]> list = new ArrayList<>();
static boolean[] visited;
static Set<String> result = new TreeSet<>();
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
ch = br.readLine().toCharArray();
st = new Stack<>();
for (int i = 0; i < ch.length; i++) {
if (ch[i] == '(') {
st.push(i);
} else if (ch[i] == ')') {
list.add(new int[] { st.pop(), i });
}
}
visited = new boolean[ch.length];
comb(0);
for (String s : result) {
sb.append(s).append("\n");
}
System.out.println(sb);
}
private static void comb(int depth) {
if (depth == list.size()) {
StringBuilder tmp = new StringBuilder();
boolean b = false;
for (int i = 0; i < ch.length; i++) {
if (!visited[i]) {
tmp.append(ch[i]);
} else {
b = true;
}
}
if (b) {
result.add(tmp.toString());
}
return;
}
comb(depth + 1);
int[] now = list.get(depth);
visited[now[0]] = true;
visited[now[1]] = true;
comb(depth + 1);
visited[now[0]] = false;
visited[now[1]] = false;
}
}복잡도
- 시간: O(2^P * N) - P는 괄호 쌍 수
- 공간: O(2^P * N)