[백준] 2800번 : 괄호 제거 - 자바[Java]

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

2800번: 괄호 제거

입력

첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개, 많아야 10개이다. 

출력

올바른 괄호 쌍을 제거해서 나올 수 있는 서로 다른 식을 사전 순으로 출력한다.

 

풀이

스택 자료구조를 사용하여 쌍이 되는 괄호를 찾아 그 괄호의 인덱스 쌍을 ArrayList<Pair> pairs에 저장한다. 올바른 괄호 쌍을 제거해서 나올 수 있는 모든 식을 찾기 위해 조합을 사용하여 제거할 괄호 쌍(인덱스 쌍)을 구하였다. 또한 해당 위치의 문자를 제거하기 위해 StringBuilder의 deleteCharAt() 메서드를 사용하였다.

 

로직

1. 스택의 push, pop 연산을 통해 올바른 괄호 쌍의 인덱스 쌍을 구한다.

2. 인덱스 쌍의 개수가 pairSize라 할 때, 크기가 1부터 pairSize인 모든 조합의 경우를 구하여 제거할 괄호 쌍(인덱스 쌍)을 선택한다.

3. 해당 조합에 저장된 숫자들을 인덱스로 정하여 그 숫자(인덱스)들을 ArrayList<Integer> numbers에 저장하고, 내림차순 정렬한다. 내림차순으로 정렬하는 이유는, 앞의 숫자를 제거하면 뒤의 숫자들의 인덱스도 변경되기 때문에 내림차순으로 정렬하여 뒤의 문자부터 제거하기 위함이다. StringBuilder의 deleteCharAt() 메서드를 사용하여 문자를 제거한다.

4. 괄호 쌍이 제거된 문자열을 ArrayList<String> answers에 저장한다.

5. 조합이 끝나면 answers를 순회하면서 답을 출력한다.

이 때 앞의 문자열과 비교하여 중복된다면 해당 문자열은 출력하지 않는다.

코드

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

public class Main {
	
	static class Blank {
		char blank;
		int idx;
		public Blank(char blank, int idx) {
			this.blank = blank;
			this.idx = idx;
		}
	}
	
	static class Pair {
		int x, y;
		public Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	static String str; // 입력한 문자열
	static int pairSize; // 괄호 쌍 개수
	static ArrayList<Pair> pairs = new ArrayList<>(); // 올바른 괄호 쌍의 인덱스 쌍
	static ArrayList<String> answers = new ArrayList<>(); // 정답 문자열

    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();
    	
    	Stack<Blank> st = new Stack<>();
    	
    	// 올바른 괄호 쌍의 인덱스 쌍 구하기
    	for (int i = 0; i < str.length(); i++) {
    		char ch = str.charAt(i);
    		if (ch == '(') {
    			st.push(new Blank(ch, i));
    		} else if (ch == ')') {
    			Blank top = st.pop();
    			pairs.add(new Pair(top.idx, i));
    		}
    	}
    	
    	pairSize = pairs.size();
    	
    	// 크기가 1 ~ pairSize인 모든 조합의 경우 구하기
    	for (int size = 1; size <= pairSize; size++) {
    		int[] comb = new int[size];
    		combination(size, 0, 0, comb);
    	}
    	
    	Collections.sort(answers);
    	bw.write(answers.get(0) + "\n");
    	for (int i = 1; i < answers.size(); i++) {
    		if (answers.get(i).equals(answers.get(i-1))) continue; // 중복된 문자열은 출력X
    		
    		bw.write(answers.get(i) + "\n");
    	}
    	
    	bw.flush();
    	br.close();
    	bw.close();
    }
    
    static void combination(int combSize, int L, int start, int[] comb) {
    	if (L == combSize) {
    		ArrayList<Integer> numbers = new ArrayList<>();
    		for (int idx: comb) {
    			Pair p = pairs.get(idx);
    			numbers.add(p.x);
    			numbers.add(p.y);
    		}
    		Collections.sort(numbers, Collections.reverseOrder());
    		deleteBlank(numbers);
    		return;
    	}
    	
    	for (int i = start; i < pairSize; i++) {
    		comb[L] = i;
    		combination(combSize, L+1, i+1, comb);
    	}
    }
    
    static void deleteBlank(ArrayList<Integer> numbers) {
    	StringBuilder sb = new StringBuilder(str);
    	for (int num: numbers) {
    		sb.deleteCharAt(num);
    	}
    	
    	answers.add(sb.toString());
    }
}

 

다른 풀이

https://loosie.tistory.com/766

sb.deleteCharAt() 대신 boolean[] check 배열을 사용하여 해당 위치의 문자는 출력하지 않도록 하였다.

또한 중복을 제거하고 사전 순으로 출력하기 위해 TreeSet<>을 사용하였다.

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

public class Main {

	static List<int[]> brackets;
	static Set<String> result;
	static boolean[] check;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = br.readLine();
		
		brackets = new ArrayList<>();
		Stack<Integer> s = new Stack<>();
		for(int i=0; i<line.length(); i++) {
			char c = line.charAt(i);
			if(c == '(') {
				s.push(i);
			}else if(c == ')'){
				brackets.add(new int[] {s.pop(), i});
			}
		}
		
		check = new boolean[line.length()];
		result = new TreeSet<>();
		comb(0, line.toCharArray());
		
		result.stream().forEach(System.out::println);
	}
	
	static void comb(int depth, char[] str) {
		if(depth == brackets.size()) {
			boolean f = false;
			StringBuilder sb = new StringBuilder();
			for(int i=0; i<str.length; i++) {
				if(!check[i]) {
					sb.append(str[i]);
				} else f = true;
			}
			if(f) { // 괄호 쌍을 1개 이상 제거했을 경우에 result에 추가
				result.add(sb.toString());
			}
			return;
		}
		
		comb(depth+1, str);
		
		int[] bracket = brackets.get(depth);
		check[bracket[0]] = true;
		check[bracket[1]] = true;
		comb(depth+1, str);
		check[bracket[0]] = false;
		check[bracket[1]] = false;
	}