BOJ 11723 : 집합

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/11723

 

bit를 이용하여 집합을 나타낼 수 있다.

int는 32 bit이기 때문에, 32개의 원소를 가진 집합을 나타낸다.

BOJ 11723은 집합 S의 원소가 20이므로 int로 선언하면 해결할 수 있다.

 

가장 낮은 자리의 비트를 1번 비트가 아닌 0번 비트라고 정의하자.

원소가 1 ~ 20이므로 0번 비트는 무시한다.

 

1) add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.

 

비트 연산 or을 이용한다. 

S |= (1 << x) : x번 비트를 1로 만든다.

or 연산이므로, 1이 있어도 1이되고, 0이 있으면 1로 바뀐다.

2) remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.

 

비트 연산 &와 ~를 이용한다.

S &= ~(1 << x) : x번째 비트를 0으로 만든다.

 

x가 5인 경우를 예로 들어보자.

 

1011 1100 = S

0010 0000 = (1 << x)

 

1011 1100 = S

1101 1111 = ~(1 << x)

--------------------------

1001 1100 = 5번 비트 제거.

 

즉, (1 << x)를 ~연산으로 하면 해당 비트를 제외하고 모두 1이 된다.

1이된 곳은 어떤 연산을 하더라도 변화가 없고, 0이된 5번 비트만 0으로 바뀐다.

 

3) check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)

 

!!(S & (1 << x))

 

먼저 S 와 x번 비트를 & 연산하자. 

S의 x번 비트가 0이라면 0이 계산되고 1이라면 (1 << x)가 나온다.

!를 붙이면 0은 1이되고 0이 아닌 수는 0이 된다.

다시 !를 붙이면 0은 0이되고, 0이 아닌 수는 1이 된다.

 

if(S & (1 << x))로 출력방법을 바꿔도 상관없다.

4) toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)

 

S ^= (1 << x)

토글 연산은 ^를 이용하면 된다. 

 

5) all: S를 {1, 2, ..., 20} 으로 바꾼다.

 

1 << 21은 10 0000 0000 0000 0000 0000가 된다.

따라서 ( 1 << 21 ) - 1은 01 1111 1111 1111 1111 1111이 된다.

0번째 비트 1은 무시하므로 총 20개의 비트가 1이 되었고 집합 all이 표시 되었다.

6) empty: S를 공집합으로 바꾼다. 

S = 0 이면 모든 bit가 0이므로 공집합으로 바꿀 수 있다.

 

어떤 변수의 bit를 확인하고 싶으면 아래처럼 print 함수를 만들면 디버깅하기 편하다.

void printbinary(unsigned int a)
{
	unsigned int mask = 1 << 31;
	for (int i = 0; i < 32;i++)
	{
		printf("%d", (a & mask) == mask);
		mask >>= 1;
		if (i % 4 == 3) printf(" ");
	}
	putchar('\n');
}

int main(void) 
{
	printbinary((1 << 21) - 1);
	return 0;
}

 

전체 코드는 아래를 참고하자.

#include <stdio.h>

int mystrcmp(const char *a, const char *b)
{
	while (*a && *a == *b) ++a, ++b;
	return *a - *b;
}

void printbinary(unsigned int a) /* 디버깅 */
{
	unsigned int mask = 1 << 31;
	for (int i = 0; i < 32;i++)
	{
		printf("%d", (a & mask) == mask);
		mask >>= 1;
		if (i % 4 == 3) printf(" ");
	}
	putchar('\n');
}

int main(void) 
{
	int M, S;
	
	scanf("%d", &M);

	S = 0;
	for (int i = 0; i < M;i++)
	{
		char str[10];
		int x;

		scanf("%s %d", str, &x);

		if (!mystrcmp(str, "add")) S |= (1 << x);
		else if (!mystrcmp(str, "remove")) S &= ~(1 << x);
		else if (!mystrcmp(str, "check")) printf("%d\n", !!(S & (1 << x)));
		else if (!mystrcmp(str, "toggle")) S ^= (1 << x);
		else if (!mystrcmp(str, "all")) S = (1 << 21) - 1;
		else if (!mystrcmp(str, "empty")) S = 0;
	}

	return 0;
}