[S5] 11723. 집합

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

11723번: 집합

이 문제는 두가지 방법으로 해결하였다. 첫번째는 문제 이름이 집합이길래 set으로 풀었다. 하지만, set보다 더 간편한 방법이 있었다. 어렵지만 쉬운 방법이다.

사실은 문제를 해결하고 나서 알고리즘 분류를 확인해보았는데, 당연히 set자료구조 일줄 알았지만, 처음보는 생소한 단어가 나를 맞이했다. 비트마스킹이라고 나와있었다. 검색을 해보니 집합을 비트로 표현할 수 있는 방법이 있었다. 예전에 자료구조 강의에서 비트맵이라고 주워들은 적이 있는데 이걸 직접 구현한다고 생각하니 약간 어지러웠지만, 직접 해보니 쉬웠다. 

우선 set을 이용한 방법을 소개하도록 하겠다.

우선 공통으로 들어가는 함수먼저 공개하겠다.

비트마스킹에 대한 알고리즘이 알고 싶은 사람은 다음 글을 참고 바란다.

https://jhcard.tistory.com/81

 

char buf[1<<20];
inline char read(){
    static int idx = 1 << 20, nidx = 1 << 20;
    if(idx == nidx){
        nidx = fread(buf, 1, 1<<20, stdin);
        if(!nidx) return 0;
        idx = 0;
    }
    return buf[idx++];
}

inline char readChar(){
    char sum;
    char now = read();
    while(now <= 32) now = read();
    sum = read();
    while(now >= 65) now = read();
    
    return sum;
}

inline int readInt(){
    int sum = 0;
    char now = read();
    while(now <= 32) now = read();
    while(now >= 48 && now <= 57) sum = sum * 10 + now - '0', now = read();
    return sum;
}

다른 곳에서 활용한 read()함수와 살짝 다르다. sum을 while문 사이에서 받고, 그 값을 반환해준다. 이유는 문제의 입력값을 확인하면 알 수 있다. 입력값으로 char형은 add, remove, check, toggle, all, empty가 있다. 이 모든것을 구분할 수 있는 방법으로 2번째에 있는 알파벳으로 충분하게 구분할 수 있다. 이것을 이용하여 sum에 d, e, h, o, l, m만을 반환하여 입력되는 문자가 어떤 명령을 요구하는지 확인할 예정이다. 

 

다음으로 set을 활용한 문제 해결 코드이다.

int main(void) {
    std::cin.tie(0); std::cout.tie(0);
    std::ios_base::sync_with_stdio(false);
    
    int M = readInt();
    std::set<int> s;
    std::set<int> tmp;
    for (int i = 1; i <= 20; i++) tmp.insert(i);

    char command;
    while (M--) {
        command = readChar();
        if (command == 'd')  s.insert(readInt());
        else if (command == 'h') std::cout << s.count(readInt()) << '\n';
        else if (command == 'e') s.erase(readInt());
        else if (command == 'o') {
            int num = readInt();
            if (s.count(num)) s.erase(num);
            else s.insert(num);
        }
        else if (command == 'l') s = tmp;
        else if (command == 'm') s.clear();
    }
}

add는 insert 함수로, check는 입력된 값이 있으면 1, 없으면 0을 반환해주는 count함수로, remove는 erase, toggle은 있으면 삭제, 없으면 추가 이므로 if문으로 확인하여 각각의 명령어를 실행해준다. all은 미리 1 ~ 20까지 저장한 tmp값을 받아주고, empty는 clear()함수로 해결해준다. set에 대한 함수가 궁금하다면 다음 글을 참고하자.

https://jhcard.tistory.com/34

[C++] set 라이브러리

여기에서 find함수는 없으면 s.end()를 가리키게 된다. 이것을 활용하여 찾았는지 못찾았는지 확인할 수 있다.

 

다음으로 비트마스킹을 활용한 방법이다. 

먼저 비트마스킹이 어떤 의미를 가지는지부터 알아보자.

그러니까 우리는 1 ~ 20까지의 숫자가 있는지 없는지를 확인하면 된다. 그러니까 다음처럼 생각해보자.

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
1	0	1	0	0	0	1	1	1	0	0	0	1	0	1	0	1	1	1	0

우리는 이것을 집합으로 표현하면 {1, 3, 7, 8, 9, 13, 15, 17,18,19}로 표현할 수 있다. 그러니까 현재 한 집합에 어떤 원소가 있다는 표현을 위의 숫자로 10100011100010101110으로 표현할 수 있다는 것이다. 이것을 이용하면 쉽게 문제 접근이 가능하다. 다음 코드를 확인하여 비교해보자.

int main(void) {
	int M = readInt();

	char command;
	int num;
	int result = 0;
	while (M--) {
		command = readChar();

		if (command == 'd') result = result | 1 << (readInt() - 1);
		else if (command == 'e') result = result & ~(1 << (readInt() - 1));
		else if (command == 'h') {
			if ((result & 1 << (readInt() - 1)) != 0) printf("1\n");
			else printf("0\n");
		}
		else if (command == 'o') result = result ^ (1 << (readInt() - 1));
		else if (command == 'l') result = (1 << 21) - 1;
		else if (command == 'm') result = 0;
	}
}