[bit masking] 11723번, 집합

오늘 소개할 문제는 백준 사이트에 있는 11723번 문제 <집합>이다.

문제는 아래 링크를 통해서 확인할 수 있다.

 

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

11723번: 집합

 

문제를 푸는 방법은 다양하지만, 여기에서는 bit masking을 사용해서 풀어보고자 한다.

 

1. 문제 파악

이전 문제에서 풀었던 [1094번, 막대기]에서 사용한 것을 생각해 보자.

이 문제에서는 2의 거듭제곱수의 값인 {1, 2, 4, 8, 16, 32, ... } 를 사용했다.

 

2021.05.22 - [코딩/백준 문제] - [bit masking] 1094번, 막대기

[bit masking] 1094번, 막대기

 

이번 문제에서는 2의 거듭제곱수의 값이 아닌, 2의 지수를 활용한다.

21bit를 그림으로 표현해 보았다. 

이 문제가 아니더라도 특정 비트 구간을 이용해서 원하는 값을 컨트롤할 수 있어야 한다.

 

bit masking

문제를 읽어보면, 1부터 20까지 집합에 추가되거나 제거를 한다고 되어 있다.

아래 그림과 같이, 노란색 음영이 된 부분에 대해서 우리는 활용하면 된다.

bit masking

예를 들면,

add 10 --> 2^10에 1를 쓴다. 

remove 10 --> 2^10에 0을 쓴다.

check 10 --> 2^10에 어떤 값이 있는지 확인해서, 있으면 1을 출력하고 없으면 0을 출력한다. 

toggle 10 --> 2^10에 1이면 0으로, 0이면 1을 쓴다.

all: 모든 비트를 1로 쓴다.

empty: 모든 비트를 0으로 쓴다.

 

예시를 들어준 부분을 코드로 보았을 때,

잘 이해가 안 된다면 비트연산자에 대해서 공부가 필요한 것이다. 

AND, OR, XOR, shift에 대해서 8bit를 기준으로 어떻게 동작하는지 확인하면 좋을 것 같다.

개념은 아는데, 쓰는 게 어렵다면, 미안하지만 모른다고 생각하는 게 맞다.

 

중간에 3항연산자( a? b: c)가 나오는데, if else 구문을 한줄로 표현한 것이다. 

a가 참이면 b를, a가 거짓이면 c를 의미한다.

코드를 보면 아래와 같다.

int main(void)
{
	int a = -1;
	int b = 1;
	int c = 0;
	int ans;

	// if else 구문
	if (a >= 0) 
	{
		ans = b;
	}
	else
	{
		ans = c;
	}

	// 3항연산자
	ans = a >= 0 ? b : c;

	return 0;
}

 

제출 코드를 확인하면, 2^0(=1) 자리에도 값을 쓰거나 지운다. 

문제에서 요청한 구간이 아니면, 개발자가 어떤 값으로 써도 상관이 없다. 

오히려 위 그림에서 21bit로 생각하고 문제를 푸는 것이 수월하다.

 

2. 제출 코드

// 11723번, 집합

#include <stdio.h>

int mstrcmp(const char * p, const char * q)
{
	while (*p && *q)
	{
		if (*p != *q) break;
		p++, q++;
	}

	return *p - *q;
}

int main(void)
{
	int M;
	int cnt;
	char cmd[10];
	int num;
	int S = 0; // S집합은 처음에 공집합이다.

	scanf("%d", &M);

	for (cnt = 0; cnt < M; cnt++)
	{
		scanf("%s %d", cmd, &num);

		if (mstrcmp(cmd, "add") == 0)
		{
			S |= 1 << num;
		}
		else if (mstrcmp(cmd, "remove") == 0)
		{
			S &= ~(1 << num);
		}
		else if (mstrcmp(cmd, "check") == 0)
		{
			printf("%d\n", (S >> num) & 1);
		}
		else if (mstrcmp(cmd, "toggle") == 0)
		{
			S = ((S >> num) & 1) ? (S & (~(1<<num))) : (S | (1<< num));
		}
		else if (mstrcmp(cmd, "all") == 0)
		{
			S = (1 << 21) - 1;
		}
		else if (mstrcmp(cmd, "empty") == 0)
		{
			S = 0;
		}
	}

	return 0;
}

 

제출하면 생각보다 빠르지 않는데, 

문자열을 비교하여 command에 따른 동작이 들어가서 그렇다. 

cmd[1]에 해당하는 문자열이 다 다르기에,

한 문자만 확인하면 시간이 줄어드는 것을 확인할 수 있다.