Study/Baekjoon

[Java] Baekjoon11723: 집합, 비트마스킹 구현

devyoseph 2022. 2. 16. 11:10

집합

1.5 초 4 MB (하단 참고) 46300 14373 10103 29.682%

문제

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

풀이

부분집합을 비트마스크로 나타낼 수 있습니다.

2의 20승이면 1048576 로 정수형의 범위를 벗어나지 않습니다.

SHIFT 연산은 기본입니다.

 

OR 연산( | ) 을 이용한 원소추가 [ add ]

x 번째 원소를 추가하기 위해서는 1을 왼쪽으로 x만큼 Shift 연산한 값과 OR 연산합니다.

101110 : 현재 부분집합의 상태 -> 4번째 원소가 비어있는데 추가하고 싶다면?

010000 : 1<<4 인 값과 OR 연산

111110

 

AND 연산으로 값 체크 [ check ]

1<<x 를 한 값과 원래 S와 AND 연산하고 만약 그 값이 0이 아니라면?

S에서도 x원소가 있다는 뜻이므로 1을 출력합니다. 만약 0이라면 없는 것이므로 0을 출력합니다.

 

AND 연산( & ) 을 이용한 원소제거 [ remove ]

x 번째 원소를 제거하기 위해서는 그 부분의 1만 없애주어야합니다.

하나만 제거하기 위해서는 &연산을 이용해야하는데 만약 1<<x 를 하게 되면 1000000의 모습입니다.

and 연산한다면 뒤 0에 의해 값들이 모두 변경되기 때문에 비트를 뒤집어줍니다.

01111111 이런 모습으로 만든다음 and 연산한다면?

0부분이 있는 쪽만 0으로 바뀌고 나머지는 1로 무사할 것입니다.

 

XOR 연산( ^ ) 을 이용한 원소토글 [ toggle ]

XOR의 성질을 이해해야합니다.

원래 원소가 1일 때 0으로 바꾸기 위해서는? 1과 XOR 연산하면 됩니다.

원래 원소가 0일 때 1로 바꾸기 위해서는? 1과 XOR 연산하면 됩니다.

즉 원래 원소가 1이든 0이든 1과 XOR 연산하면 그 반대가 나옵니다.

그와 반대로 원소가 무엇이든 0과 XOR 연산하면 그대로 나옵니다.

 

이 성질을 이용해 1<<x 값과 XOR연산을 수행합니다.

 

NOT 연산을 이용한 모든 원소 추가 [ all ]

원소가 하나도 없는 상태는 0으로 표현합니다.

모든 원소가 있도록 하려면 0을 뒤집습니다.

S = ~0

 

전체 코드

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


public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		int M = Integer.parseInt(br.readLine());
		int S = 0;
		while(M-->0) {
			st = new StringTokenizer(br.readLine());
			
			switch(st.nextToken()){
				case "add": // OR 연산으로 추가합니다
					S |= 1<<Integer.parseInt(st.nextToken());
					break;
				case "remove": // 비트를 뒤집고 AND 연산
					S &= ~(1<<Integer.parseInt(st.nextToken()));
					break;
				case "check": // AND 연산으로 확인
					sb.append((S & 1<<Integer.parseInt(st.nextToken()))!=0?1:0).append("\n");
					break;
				case "toggle": // 원래 원소가 1이든 0이든 1과 XOR 연산하면 그 반대가 나옵니다.
					S ^= 1<<Integer.parseInt(st.nextToken());
					break;
				case "all":
					S |= ~0;
					break;
				case "empty": S = 0; break;
			}
		}
		System.out.println(sb.toString());
	}
}

저작자표시