[백준 2800번] 괄호 제거

문제 링크: 2800번 제목

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

 

처음의 고민

사전 순 출력이 무엇인가에 대해서 헤맸었는데, 그냥 말 그대로 sort()를 이용하면 되는 것이었다. 즉 처음부터 사전 순으로 만들기 위해서 노력할 필요가 없이, 그냥 각 괄호를 출력하거나 출력하지 않는 경우(단 모든 괄호를 출력하는 경우는 제외)를 모두 하나의 배열에 문자열로 저장하여 이를 정렬하여 출력하면 된다.

 

구현 과정의 고민

아마 본래는 비트마스크를 쓰는 문제가 아닐까 하는데... 빨리 배워야겠다.

처음에 문자열을 읽어나가는 과정에서부터 왼쪽 괄호와 오른쪽 괄호의 인덱스를 저장한다. 쌍을 맞추기 위해서, 왼쪽 괄호의 인덱스를 스택에 쌓아나가다가, 인덱스 i에서 오른쪽 괄호를 만나면 lparen에 stack.pop()을 저장하고, rparen에는 i를 저장한다.

한편 아래와 같은 겹괄호, 즉 수학적으로 무의미한 괄호에 대해서는 안쪽 괄호가 생략되나 바깥쪽 괄호가 생략되나 출력 결과도 같다.

((11+5))

이것을 처음에 겹괄호를 없애려고 해서 고생했는데, 그냥 집합에 넣어줬다가 다시 리스트로 바꿔서 출력하면 중복원소가 제거된다. 물론 이것이 조금 더 느리겠지만, 이 정도까지만 하면 통과할 수 있게 채점 기준이 널널했다.

 

import java.util.ArrayList;
import java.util.Stack;
import java.util.Collections;
import java.util.Scanner;
import java.util.Set;
import java.util.HashSet;

public class Main {
	static ArrayList<Character> sentence = new ArrayList<Character>();
	static ArrayList<Integer> lparen = new ArrayList<Integer>(); // '('가 위치한 인덱스. 앞쪽이 깊은 괄호임
	static ArrayList<Integer> rparen = new ArrayList<Integer>(); // ')'가 위치한 인덱스. 앞쪽이 깊은 괄호임
	static ArrayList<Boolean> toOmit = new ArrayList<Boolean>(); // [true, ..., true] (size: parenNum)
	static ArrayList<StringBuilder> answers = new ArrayList<StringBuilder>();
	static int parenNum; // 괄호 쌍의 개수
	
	/* toOmit에 들어있는 인덱스를 제외하고는 식 전체를 출력 */
	public static void printSentence(ArrayList<Boolean> toOmit) {
		/* 출력하지 말아야 할 인덱스를 저장한다. */
		Set<Integer> noPrint = new HashSet<Integer>();
		for (int i = 0; i < toOmit.size(); i++) {
			if (toOmit.get(i)) continue;
			noPrint.add(lparen.get(i));
			noPrint.add(rparen.get(i));
		}
		
		/* 원래 식과 같은 경우는 생략한다. */
		if (noPrint.isEmpty()) return;
		
		/* 출력하지 말아야 할 인덱스 빼고는 모두 출력한다. */
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < sentence.size(); i++) {
			// 현재 인덱스가 출력하지 말아야 할 인덱스라면
			if (noPrint.contains(i)) continue;
			
			// 현재 인덱스가 출력해야 할 인덱스라면
			char cur = sentence.get(i);
			sb.append(cur);
		}
		answers.add(sb);
	}
	
	public static void omitParen(int idx, ArrayList<Boolean> toOmit) {
		if (idx == parenNum) {
			printSentence(toOmit);
			return;
		}
		
		toOmit.set(idx, true); // idx 깊이의 안쪽 괄호를 생략함
		omitParen(idx+1, toOmit);
		toOmit.set(idx, false); // idx 깊이의 안쪽 괄호를 생략하지 않음
		omitParen(idx+1, toOmit);
	}
	
	public static void main(String[] args) {
		/* input */
		Scanner sc = new Scanner(System.in);
		String str = sc.next();
		sc.close();
		
		Stack<Integer> stack = new Stack<Integer>();
		for (int i = 0; i < str.length(); i++) {
			char cur = str.charAt(i);

			// 문자열을 리스트로
			sentence.add(cur);
			
			// 괄호 인덱스 추가
			if (cur == '(') stack.push(i);
			if (cur == ')') {
				lparen.add(stack.pop());
				rparen.add(i);
			}
		}
		
		// set parenNum
		parenNum = lparen.size();
		// set toOmit
		for (int i = 0; i < parenNum; i++) {
			toOmit.add(true);
		}
		
		/* print */
		omitParen(0, toOmit);
		
		/* remove duplicated Strings */
		Set<String> set = new HashSet<String>();
		for (StringBuilder sb : answers)
			set.add(sb.toString());
		ArrayList<String> newLs = new ArrayList<String>(set);
		
		/* sort and print */
		StringBuilder answer = new StringBuilder();
		Collections.sort(newLs);
		for (String ans : newLs) {
			answer.append(ans);
			answer.append("\n");
		}
		System.out.print(answer);
	}
}