2800괄호제거

이상하네 벨로그에 올린줄 알았는데 안올렸네

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

https://hsin.hr/coci/archive/2011_2012/
콘테스트 6
테스트데이타 받고 ZAGRADE 폴더에서 테스트 케이스 볼 수 있다

틀린경우가 많이 나와서 테스트 케이스 일일이 비교해서 겨우 풀었다

이문제의 경우에 어떻게 풀지 생각이 떠올랐는데
(1+(2*(3+4)))
위의 예제의 경우 출력의 경우 8가지 라는 부분에서 비트 논리 연산이 떠올랐다. 괄호쌍의 개수가 3개인데 출력개수는 총 8가지라는건 2^3 = 8 이 연상된다. 물론 답은 7가지 제출하면된다. 그래서 나는 N-2 부터 0까지 for 문을 돌리면서 비트논리연산을 활용해 출력하였다.
예를들어 N이 8 라면 for문을 돌릴때 6(110), 5(101), 4(100), 3(011), 2(010), 1(001), 0(000) 순서대로 감소하게 하였다 그리고 각각의 괄호쌍 a,b,c를 (100), (10), (1) 비트값으로 연결시키고 for문을 돌릴때 & 연산을 통해 출력할지를 조절하였다.

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

public class Main
{

    public static void main(String[] args)
    {
        FastReader fr = new FastReader();

        String command = fr.nextLine();

        HashMap<Integer, Integer> map = new HashMap<>();

        ArrayList<Integer> keyList = new ArrayList<>();

        for(int i = 0; i < command.length(); ++i)
        {
            if(command.charAt(i) == '(')
                keyList.add(i);
            else if(command.charAt(i) == ')')
            {
                int key = keyList.remove(keyList.size()-1);
                map.put(key, i);
            }
        }

        int pairCnt = map.size();
        int pairCntCopy = pairCnt-1;
        int max = (int)Math.pow(2, pairCnt);

        StringBuilder sb = new StringBuilder();
        HashSet<Integer> renderKey = new HashSet<>();
        HashSet<String> hash = new HashSet<>();
        for(int i = max-2; i >= 0; --i)
        {
            sb.setLength(0);
            renderKey.clear();
            pairCntCopy = pairCnt-1;
            for(int key : map.keySet())
            {
                int cur = (int)Math.pow(2, pairCntCopy);
                if((i & cur) != 0)
                {
                    renderKey.add(key);
                    renderKey.add(map.get(key));
                }

                pairCntCopy--;
            }

            for(int j = 0; j < command.length(); ++j)
            {
                if(command.charAt(j) == '(' || command.charAt(j) == ')')
                {
                    if(renderKey.contains(j) == false)
                        continue;
                }

                sb.append(command.charAt(j));
            }

            sb.append("\n");

            if(false == hash.contains(sb.toString()))
            {
                hash.add(sb.toString());
            }

        }
        hash.stream().sorted((s1, s2) -> s1.compareTo(s2)).forEach(s -> System.out.print(s));

    }

    static class FastReader
    {
        BufferedReader br;
        FastReader()
        {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String nextLine()
        {
            String str = "";

            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }

    }
}