[백준 - 2800] 골드5 - 괄호 제거 (문자열)

www.acmicpc.net/problem/2800

2800번: 괄호 제거

 

1. 유형

부분집합, 스택

 

2. 풀이

1) 괄호를 아래와 같이 쌍별로 분류한다.

(	(	)	(	)	)
1	2	2	3	3	1

2) 부분집합

배열을 처음부터 탐색하면서 '(' 괄호가 나오면 선택, 비선택을 나누어 부분집합을 구한다

 

3. 코드

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

public class Main {
	static String str;
	static List<String> list;
	static Set<String> set;
	static int[] arr;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		str = st.nextToken();
		list = new ArrayList<>();
		arr = new int[str.length()];
		set = new HashSet<>();
		int index=1;
		for(int i=0; i<str.length(); i++) {
			if(str.charAt(i)=='(')
				arr[i] = index++;
			else if(str.charAt(i)==')')
				arr[i] = --index;
		}
		dfs(0, new Stack<>(), new String());
		list.addAll(set);
		Collections.sort(list);
		for(int i=1; i<list.size(); i++)
			System.out.println(list.get(i));
	}
	static void dfs(int dep, Stack<Integer> stack, String s) {
		if(dep == str.length()) {
			set.add(s);
			return;
		}
		if(str.charAt(dep)=='(') {
			stack.add(arr[dep]);
			dfs(dep+1, stack, s+'(');
			stack.pop();
			dfs(dep+1, stack, s);
		}
		else if(str.charAt(dep)==')') {
			if(!stack.isEmpty() && stack.peek() == arr[dep]) {
				stack.pop();
				dfs(dep+1, stack, s+')');
				stack.add(arr[dep]);
			}else
				dfs(dep+1, stack, s);
		}else {
			dfs(dep+1, stack, s+str.charAt(dep));
		}
	}
	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}