백준 11723번 : 집합(Java)

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

11723번: 집합

---

[풀이]

• 배열 혹은 비트마스크를 이용한 문제입니다.
• 처음에는 Java의 Set 자료구조를 이용했는데 시간초과가 발생했습니다. (M이 1 <= M <= 3000000)의 범위라서 당연히 시간 초과에 유의해야 합니다.
• 고민을 하다가, 다른 블로그들을 참조하니 대부분 비트마스크를 이용해서 구현한 것을 확인했습니다.
  • 배열로 표현을 할 때 {1,3,5,7} 을 1010101(2)로 표현을 할 수 있습니다. 이러한 방식을 적용합니다.
  • 저도 이번 기회에 비트마스크 복습을 해야할 필요성을 느껴 이전에 메모해 둔 비트 마스크 필기를 다시 봐야할 것 같습니다..

---

[코드]

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int m = Integer.parseInt(br.readLine());
		int bitmask = 0;
		StringBuilder sb = new StringBuilder();
		
		while(m-- > 0){
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			String order = st.nextToken();
			
			switch (order){
				case "all" :
					bitmask = (1 << 21) - 1;
					break;
				case "empty" :
					bitmask = 0;
					break;
				default:
					int value = Integer.parseInt(st.nextToken());
					switch (order){
						case "add" :
							bitmask |= (1 << value);
							break;
						case "remove" :
							bitmask &= ~(1 << value);
							break;
						case "check" :
							sb.append((bitmask & (1 << value)) != 0 ? 1 : 0).append("\n");
							break;
						case "toggle" :
							bitmask ^= (1 << value);
							break;
					}
			}
		}
		bw.write(sb.toString());
		bw.close();
	}
}