백준 [C언어] 11723 : 집합

✅ 문제

✅ 해결 과정

1. 메모리 제한이 있으므로 집합 구현 시 배열이 아닌 비트 벡터를 이용한다.

2. add: 집합 | 원소

    remove: 집합 =& ~원소

    check: 집합 & 원소 == 0이면 0, 그렇지 않으면 1 반환

    toggle: check()결과가 0이면 add(), 1이면 remove()

    all: 1~20 돌면서 toggle(s, i)

    empty: *s = (BitSet)0

 

✅ 코드

#include <stdio.h>
#include <string.h>

typedef unsigned long BitSet; 
//비트벡터집합의 자료형 (unsigned long)

#define BitSetNull (BitSet)0  
//공집합(모든 비트가 0)
#define BitSetBits 21  
//유효 비트 수 
#define SetOf(no) ((BitSet)1 << (no)) 
//원소가 no인 집합 {no} : 가장 아래쪽 비트 값이 1인 집합 {0} 에서 비트를 왼쪽으로 no만큼 shift

/*집합 s에 원소 n있는지 확인*/
int check(BitSet s, int n)
{
  if(s & SetOf(n)) return 1;  //집합 s와 집합 {n}의 논리곱 연산 : 0이면 
  else return 0;
}

/*집합 s에 n 추가*/
void add(BitSet *s, int n)
{
  *s |= SetOf(n); //{n} 과  집합s 비트 or연산해서 없으면 추가되고 있으면 변함x
}

/*집합 s에 n 삭제*/
void Remove(BitSet *s, int n)
{
  *s &= ~SetOf(n);  //있으면 삭제되고 없으면 변함X
}

void toggle(BitSet *s, int n)
{
  if(check(*s, n)) Remove(s, n);
  else add(s, n);
}

void all(BitSet *s)
{
  for(int i = 1; i <= 20; i++)
    {
      toggle(s, i);
    }
}

void empty(BitSet *s)
{
  *s = BitSetNull;
}

/*집합 s의 원소 개수(1인 것들의 개수) 반환*/
int Size(BitSet s)
{
  //s-1하면 s에서 첫 1이 나올 때까지 하위 비트들이 0->1로 바뀌고 첫 1비트는 1->0으로 바뀜. 따라서 s와 s-1을 비트AND연산 하면 ==> 첫 1비트가 0비트로 바뀌는 것. 
  //이때마다 카운트하면 그게 1비트 개수임.
  int n = 0;  //원소 개수
  for(; s != BitSetNull; n++) //공집합될 때까지 반복
  {
    s &= s-1;
  }
  return n;
}

/*집합 s의 모든 원소 출력*/
void Print(BitSet s)
{
  int i;
  //printf("{ ");
  for(i=0; i < BitSetBits; i++) //전체 32비트 돌면서
  {
    if(check(s, i)) //i라는 원소가 존재하면 그 원소 출력
      printf("%d ", i);
  }
  //printf("}");
}

/*집합 s의 모든 원소 출력(줄바꿈 문자 포함)*/
void PrintLn(BitSet s)
{
  Print(s);
  putchar('\n');
}

int main()
{
  int M;
  scanf("%d", &M);
  char cal[7];
  int data;

  BitSet s = BitSetNull;
  
  while(M>0)
    {
      scanf("%s", cal);
      scanf("%d", &data);

      if(strcmp(cal, "add") == 0)
      {
        add(&s, data);
      }
      else if(strcmp(cal, "check") == 0)
      {
        printf("%d\n", check(s, data));
      }
      else if(strcmp(cal, "remove") == 0)
      {
        Remove(&s, data);
      }
      else if(strcmp(cal, "toggle") == 0)
      {
        toggle(&s, data);
      }
      else if(strcmp(cal, "all") == 0)
      {
        all(&s);
      }
      else if(strcmp(cal, "empty") == 0)
      {
        empty(&s);
      }
      M--;
    }
  return 0;
}

❗️ 맞았습니다!