[백준] 11723. 집합 (JAVA)

📚 집합

 

이 문제의 경우 비트마스킹과 StringBuilder를 사용하지 않으면 시간초과가 발생한다.

 

---

문제

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

• add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
• remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
• check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
• toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
• all: S를 {1, 2, ..., 20} 으로 바꾼다.
• empty: S를 공집합으로 바꾼다. 

 

입력

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

 

출력

check 연산이 주어질때마다, 결과를 출력한다.

 

---

💡  나의 풀이

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Main {
	static int S = 0;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int line = Integer.parseInt(br.readLine());

		for(int i=0; i<line; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String cmd = st.nextToken();
			int elm;
			if(st.hasMoreTokens())
				elm = Integer.parseInt(st.nextToken());
			else elm = 0;
			operate(cmd, elm);
		}

		System.out.println(sb.toString());
	}

	private static void operate(String cmd, int elm) {
		switch(cmd) {
			case "add":
				add(1 << (elm-1));
				break;
			case "remove":
				remove(~(1 << (elm-1)));
				break;
			case "check":
				check(1 << (elm-1));
				break;
			case "toggle":
				toggle(1 << (elm-1));
				break;
			case "all":
				all();
				break;
			case "empty":
				empty();
				break;
		}
	}

	private static void add(int elm) {
		S |= elm;
	}

	private static void remove(int elm) {
		S &= elm;
	}

	private static void check(int elm) {
		sb.append(((S & elm) == elm) ? "1\n" : "0\n");
	}

	private static void toggle(int elm) {
		S ^= elm;
	}

	private static void all() {
		S |= ~0;
	}

	private static void empty() {
		S = 0;
	}
}

int 자료형의 크기는 32bit로, 하나의 int형 변수를 선언하여 32개 원소의 포함여부를 체크할 수 있다.

 

이 문제에서는 1부터 20까지를 집합의 원소로 가질 수 있으므로,

메모리 관리 측면에서 int형 변수 하나로 비트연산을 하는 것이

길이 20짜리 int형 배열을 선언하여 연산하는 것 보다 20배나 효율적이다. 

 

 

---

 

11723번: 집합