[비트마스크] 백준 - 집합

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

11723번: 집합

 

-문제해설

처음에 ArrayList에 값을 넣어서 풀었더니 시간초과가 나왔다...

그 다음에는 문제에서 집어넣은 값을 다시 출력하라는 말은 없기 때문에 add되는 값을 배열의 인덱스로 설정해서 풀어보려고 했는데 비트마스크를 이용하면 효율적으로 풀 수 있다는 글을 보았다.

 

결국 비트마스크를 공부한 뒤 문제를 풀 수 있었다.

비트마스크에 대해 공부한 내용을 간략히 정리하면

 

이 문제의 경우 입력받은 값을 그대로 출력하라는 조건은 없고 check명령일 경우 단순히 있으면 1 없으면 0을 출력하기 때문에 배열의 인덱스에 값을 넣어서 풀 수도 있다. 

예를 들어서 간단하게 크기가 4인 arr배열이 있다고 해보자.

int[] arr = new int[5];

add 1 은 arr[1] = T ( arr = [ F, T, F, F, F ] )

add 2 은 arr[2] = T ( arr = [ F, T, T, F, F ] )

add 3 는 arr[3] = T ( arr = [ F, T, T, T, F ] )

add 4 는 arr[4] = T ( arr = [ F, T, T, T, T ] )

 

근데 이렇게 배열을 선언하고 각 인덱스를 T 또는 F로 만들어주는 것보다 2진수를 활용하면 이를 손쉽게 나타낼 수 있다.

현재 arr배열이 arr = [ F, T, T, T, T ] 이므로 앞에 F빼고 T를 이진수로 단순히 바꾸면 1111이다.

만약 여기에 add 5 명령이 입력되면 배열의 인덱스로 따지면 arr = [ F, T, T, T, T, T ]가 되도록 해야 한다.

(배열의 크기는 잠시 무시 ㅎ)

이를 위와 같이 이진수로 바꾸면 11111이 된다.

 

즉, add 6이되면 111111이 되어야 하고 만일 이전에 입력된 add 4가 되도 이미 오른쪽에서 4번째 자리에 1이 있으므로 문제에 조건과 부합되게 명령이 무시된다.

 

그러면 다시 1111에서 add 5를 했을 때 11111로 어떻게 만들어야 할까

이때 사용되는 것이 비트마스크이다.

기존 1111에서 10000과 or연산을 하면 11111이 된다.

or연산은 둘 중 하나라도 값이 1이면 1이 되기 때문이다.

 

   1111

| 10000

ㅡㅡㅡㅡ

  11111

 

그러면 10000은 어떻게 만들까? 바로 쉬프트 연산자를 이용해서 만들 수 있다. 

쉬프트 연산자는 << 또는 >> 식으로 나타내고 

 

만약 1<<3 이면 1을 왼쪽으로 3비트 민다는 의미이다.

즉

1을 왼쪽으로 3비트 밀면 1000로 된다.

 

10000을 만들기 위해서는 1<<4가 되어야 하므로 1<<(5-1)이 되면 된다.

 

 

이번에는 remove연산을 확인해본다.

11111에서 remove 5 명령이 들어올 경우 01111로 만들어줘야한다. 그러기 위해서는 맨 앞에 1만 0으로 바꾸고

나머지 값들은 원래 값을 유지해야 한다.

이때는 not과 and 연산을 이용한다.

 

먼저 쉬프트 연산자로 아래와 같이 만든다. ( 1<<(5-1) )

   11111

   10000

 

그리고 not연산을 한다.

   11111

   01111

 

다음으로 and 연산을 한다.

    11111

 & 01111

ㅡㅡㅡㅡㅡㅡ

    01111

 

toggle의 경우는 xor연산을 이용해야 한다. xor연산은 같으면 0, 다르면 1을 반환한다.

1111에서 toggle 4 명령이 들어왔을 경우 왼쪽 첫 번째 자리가 있으면 삭제, 없으면 추가해야된다.

 

 

따라서 먼저 쉬프트 연산을 하고( 1<<(4-1) )
    1111

    1000

 

xor연산을 한다.

    1111

 ^ 1000

ㅡㅡㅡㅡㅡ

    0111

 

다시 toggle 4를 하면

    0111

 ^ 1000

ㅡㅡㅡㅡㅡ

    1111

이 된다.

 

나머지는 코드를 보면 이해가 될 것 같다!

 

 

 

-자바

package implementation;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class BJ11723 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int m = Integer.parseInt( br.readLine() );
		
		StringBuffer sb = new StringBuffer();
		StringTokenizer st;
		String order;
		int x;
		int bitMask = 0;
		
		while( m --> 0 ) {
			x = 0;
			st = new StringTokenizer( br.readLine() );
			order = st.nextToken();
			if( st.countTokens()==1 ) x = Integer.parseInt( st.nextToken() );
			
			switch( order ) {
				case "add":
					bitMask = bitMask | 1<<(x-1);
					break;
					
				case "remove":
					bitMask = bitMask & ~( 1<<(x-1) );
					break;
					
				case "check":
					sb.append( ( ( bitMask & 1<<(x-1) ) == 1<<(x-1) ? 1:0) + "\n" );
					break;
					
				case "toggle":
					bitMask = bitMask ^ 1<<(x-1);
					break;
					
				case "all":
					bitMask = ~0;
					break;
					
				case "empty":
					bitMask = 0;
					break;
			}
		}
		System.out.println( sb );
	}
}

 

-파이썬

import sys
l = sys.stdin.readline
print = sys.stdout.write
t = int( l() )

bitMask = 0
for _ in range( t ):
    Order, *arr = l().split()
    if arr: x = int( arr[0] )
    
    if Order == "add": bitMask = bitMask | (1<<(x-1))
    elif Order == "remove": bitMask = bitMask & ~(1<<(x-1))
    elif Order == "check": print( "1\n" if bitMask & (1<<(x-1)) == 1<<(x-1) else "0\n" )
    elif Order == "toggle": bitMask = bitMask ^ (1<<(x-1))
    elif Order == "all": bitMask = ~0
    else: bitMask = 0   #empty