[백준] 2800. 괄호 제거 (자바 JAVA)

[ 문제 ]  [백준] 2800. 괄호 제거 (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/2800

2800번: 괄호 제거

---

# 접근 방법 및 풀이 

 

• 문자열 + 스택 + 재귀 문제다. 
• 정답률이 33퍼로 낮길래 일단 풀고 봤더니 틀렸다. 반례 찾아보니, 답에 중복이 있다면 제거해주어야한다. 이부분때문에 정답률이 낮은 것 같다.
• 먼저 풀이는 다음과 같다.
• 1. 스택으로 "괄호 쌍 인덱스" 리스트에 담아주기
• 2. 리스트에서 제거할 괄호 뽑기. -> 부분집합
• 3. 제거할 괄호 인덱스 제외하고, 남은 문자열로 새로운 문자열을 만들어 TreeSet에 담기
• 새로 만들어진 문자열의 중복을 제거하기 위해 Set을 사용했고, 정렬도 함께 되도록 TreeSet을 이용했다.
• 부분집합으로 재귀 돌릴 경우  FFFF <- 와 같이 "다 선택 안하는 공집합일 경우" 새로운 문자열을 만들었을때 원래 문자열과 길이가 같기때문에 이부분 제외하고 Set에 넣어줬다.
• 자세한건 코드참조

# 주의할 점 

 

• 중복되는 값 제거할 것! 
• 반례로, (((1)))(2) 해보면 된다.

 

JAVA 코드

package Gold;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;

public class bj2800_괄호제거 {
	static char arr[];

	static class Node {
		int idx;
		char c;

		public Node(int idx, char c) {
			this.idx = idx;
			this.c = c;
		}
	}

	static List<Point> list;
	static boolean sel[];
	static Set<String> ans;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		arr = in.readLine().toCharArray();
		Stack<Node> stack = new Stack<>();
		list = new ArrayList<Point>();
		for (int i = 0; i < arr.length; i++) {
			char c = arr[i];
			if (c == '(')
				stack.add(new Node(i, c));
			if(c == ')') {
				Node node = stack.pop();
				list.add(new Point(node.idx, i));
			}
		}
		ans = new TreeSet<String>();
		sel = new boolean[list.size()];
		powerSet(0);
		for (String s : ans) {
			System.out.println(s);
		}
	}
	private static void powerSet(int idx) {
		if(idx == sel.length) {
			StringBuilder sb = new StringBuilder();
			boolean check[] = new boolean[arr.length];
			for (int i = 0; i < sel.length; i++) {
				if(sel[i]) {
					check[list.get(i).x] = true;
					check[list.get(i).y] = true;
				}
			}
			for (int i = 0; i < arr.length; i++) {
				if(!check[i])
					sb.append(arr[i]);
			}
			if(sb.length() != arr.length)
				ans.add(sb.toString());
			return;
		}
		sel[idx] = true;
		powerSet(idx+1);
		sel[idx] = false;
		powerSet(idx+1);	
	}
}

 

 

 

REVIEW