[JAVA / 자바] 백준 11723번 - 집합 (실버 5)

 문제 

비어있는 공집합 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 연산이 주어질 때마다, 결과를 출력한다.

---

---

 문제 접근 방법 

이번 문제는 데이터의 저장, 탐색, 수정이 많이 이루어져서 시간 내에 입력에 관한 모든 명령을 실행해야 하는 문제이다.

따라서 저장, 탐색, 수정 연산이 빨라야 하는데 중복된 값의 입력이 없으므로 HashSet을 먼저 떠올려 볼 수 있다.

그러나 또 다른 방법 중 하나는 비트 마스킹(Bit Masking)이라는 방법도 사용할 수 있다.

비트 마스킹은 다른 자료형을 사용하는 것보다 1. 수행 시간이 빠르고, 2. 코드가 짧고, 3. 메모리 사용량이 적다는 장점이 있다.

따라서 HashSet과 비트 마스킹 두 가지 방법으로 코드를 구현해 보겠다.

---

 JAVA 코드 풀이 

1. 비트 마스킹(Bit Masking)

2. HashSet

 코드 실행 결과 

1. 비트 마스킹 코드 실행 결과

2. HashSet 코드 실행 결과

---

 후기 

HashSet도 데이터 저장, 탐색, 수정에 관해 정말 빠르지만, 비트 마스킹이 그보다 더 연산이 빠른 것을 알 수 있다. 이를 미루어 보았을 때, 나중에 시간이 아쉬운 상황과 코드가 너무 길어지거나 메모리가 부족한 경우에서는 비트 마스킹도 연습해서 나중에 사용할 수 있게 만들어야겠다는 생각이 든다.

---

 문제 원본 

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

11723번: 집합

 알고리즘 분류 

• 구현
• 비트 마스킹