[Baekjoon] 2800_괄호 제거

Gold IV

문제(출처: https://www.acmicpc.net/problem/2800)

---

< 괄호 제거 >

 

문제 풀이 

 

괄호 쌍을 미리 찾은 후 괄호를 제거하거나 제거하지 않는 모든 경우를 판단한다.

 

 my solution (Java)

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.Stack;

public class _2800_ { // 괄호 제거
	static ArrayList<String> list;
	static ArrayList<Integer> check;
	static int num[];

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

		String str = bf.readLine();

		num = new int[str.length()];

		Stack<Integer> temp = new Stack<>();
		check = new ArrayList<>();
		for (int i = 0; i < str.length(); i++) {
			if (str.charAt(i) == '(') {
				temp.add(i);
			} else if (str.charAt(i) == ')') {
				int n = temp.pop();
				check.add(i);
				num[i] = n;
				num[n] = i;
			}
		}

		list = new ArrayList<>();
		boolean arr[] = new boolean[str.length()];
		search(str, 0, arr);

		Collections.sort(list);
		for (int i = 0; i < list.size(); i++) {
			bw.write(list.get(i) + "\n");
		}
		bw.flush();

	}

	private static void search(String str, int idx, boolean[] arr) {
		if (idx == check.size()) {
			String result = "";
			for (int i = 0; i < str.length(); i++) {
				if (arr[i]) {
					continue;
				}
				result += str.charAt(i);
			}

			if (!list.contains(result) && !result.equals(str))
				list.add(result);
			return;
		}

		arr[num[check.get(idx)]] = true;
		arr[check.get(idx)] = true;
		search(str, idx + 1, arr);
		arr[num[check.get(idx)]] = false;
		arr[check.get(idx)] = false;
		search(str, idx + 1, arr);
	}
}

변수)
str : 수식
num : 괄호 쌍
temp : 괄호 쌍 찾기 위한 stack
check : ')' 위치
list : 올바른 괄호 쌍을 제거해서 나올 수 있는 서로 다른 식
arr : 괄호 제거 여부

 

수식을 입력받는다. 수식을 살펴보며 괄호 쌍을 찾아 num 배열에 저장한다. 또한, 닫는 괄호 위치를 ArrayList에 저장한다. search 함수를 호출해 올바른 괄호 쌍을 제거해서 나올 수 있는 서로 다른 식을 찾는다. list를 정렬 후 출력한다.

 

search(수식, idx, 괄호 제거 여부)

닫는 괄호 위치를 담은 ArrayList를 다 돌았다면 arr배열을 살펴보며 괄호를 제거한다. 제거한 후 만들어진 수식이 list에 없거나 원래 주어진 식과 일치하지 않다면 list에 추가한 후 종료한다.

 

check ArrayList에 들어있는 닫는 괄호 위치를 살펴보며 괄호를 제거하는 경우와 제거하지 않는 경우 둘 다 계산한다. 괄호를 제거하는 경우에는 닫는 괄호와 그 쌍인 여는 괄호 위치를 arr 배열에서 true로 저장한 후 search 함수를 호출한다. 괄호를 제거하지 않는 경우에는 false로 저장한 후 search 함수를 호출한다.

 

* 메모리 초과 해결 방법

닫는 괄호 위치를 미리 ArrayList에 담아 그 ArrayList에 담겨있는 값만 확인하도록 구현했다.

---

---