[BOJ-2800][문자열 처리/비트 마스킹/스택] 괄호 제거 - Java

문제 바로가기

2800번: 괄호 제거

약간 카카오스러운 문제라고 생각합니다.

막 엄청 고오급 알고리즘을 요하는 문제는 아니지만 구현하는데 쪼끔 애먹었습니다..

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();

        Map<Integer, Integer> paren = new HashMap<>();
        List<Integer> parenIdx = new ArrayList<>();
        Stack<Integer> s = new Stack<>();
        for (int i = 0; i < input.length(); i++) {
            if (input.charAt(i) == '(') {
                s.push(i);
                parenIdx.add(i);
            }else if(input.charAt(i) == ')') {
                paren.put(s.pop(), i);
            }
        }
        Set<String> set = new HashSet<>();

        for (int i = 1; i < (1 << parenIdx.size()); i++) {
            StringBuilder sb = new StringBuilder();
            Map<Integer, Integer> idx = new HashMap<>();

            // 부분집합 만들기
            for (int j = 0; j < parenIdx.size(); j++) {
                if ((i & (1 << j)) != 0) {
                    idx.put(parenIdx.get(j), paren.get(parenIdx.get(j)));
                }
            }

            for (int k = 0; k < input.length(); k++) {
                // 빼야 할 괄호
                if (input.charAt(k) == '(' && idx.containsKey(k)) continue;
                if (input.charAt(k) == ')' && idx.containsValue(k)) continue;

                sb.append(input.charAt(k));
            }
            set.add(sb.toString());
        }
        List<String> output = new ArrayList(set);

        output.sort(Comparator.naturalOrder());
        for(int i = 0; i < output.size(); i++)
            System.out.println(output.get(i));
    }
}

우선 괄호의 쌍을 해시맵으로 저장했습니다.

이때는 스택을 이용해서 괄호의 쌍을 체크해줍니다.

 

그리고 부분집합을 인덱스로 만들어서 접근해주기 위해서 parenIdx란 리스트도 하나 두었습니다.

여기는 여는 괄호의 인덱스가 들어갑니다.

좀 더 간결하게 할 수 있는 아이디어가 있으시면 댓글로 알려주세욥!

 

 

부분집합은 비트 마스킹을 이용해서 만들어 보았습니다.

십진수	이진수	{1, 2, 3}
0	000	{ }
1	001	{1}
2	010	{2}
3	011	{1, 2}
4	100	{3}
5	101	{1, 3}
6	110	{2, 3}
7	111	{1, 2, 3}

이런 식으로 부분집합을 표현해 주는겁니다.

 

코드는 이렇습니다.

for (int i = 0; i < (1 << n); i++) {		// (1 << n) : 부분집합의 개수
	for (int j = 0; j < n; j++) {			// 원소의 개수만큼 비트 비교
		if ((i & (1 << j)) != 0) {
			// i의 j번 째 비트가 1 이면 j번 째 원소 출력!
		}
	}	
}

 

이렇게 괄호의 쌍들에 대한 부분집합을 만들어서 인풋으로 들어온 문자열 길이만큼 돌면서 봐줍니다.

'('나 ')'이고 얘가 있는 위치(인덱스)가 부분집합 해시맵에 들어 있으면 그 친구들은 빼고 StringBuilder에 척척 넣어주면 됩니다.

 

이 로직대로 제출하면

틀렸습니다. 가 뜹니다.

 

그것은 바로 중복 값이 나올 수 있기 때문임니다.

e.g) ((((0))))

 

따라서 좀 지저분하지만... Set에 넣어서 중복값을 빼주고 또 정렬해야 되니깐... List에 다시 넣어서 정렬하고 출력했습니다...

 

 

휘유 감사합니다. 3.3