BOJ) 집합 (11723 번)

집합

11723번: 집합

 

 

문제 조건

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
all: S를 {1, 2, ..., 20} 으로 바꾼다.
empty: S를 공집합으로 바꾼다. 

 

조건을 보면 그리 어렵지 않다고 생각이 든다. 하지만, 메모리 제한이 4 MB로 아주 작기 때문에 일반적인 방법으로 접근하면 메모리 초과가 뜰 것이다. 이 문제는 비트 마스크를 이용해서 풀어야하는 문제다.

위키를 살펴보면 비트 마스크에 대해 다음과 같이 정의하고 있다.

컴퓨터 과학에서 마스크(mask) 또는 비트마스크(bitmask)는 특히 비트 필드에서 비트 연산에 사용되는 데이터이다. 마스크를 사용하면 바이트, 니블, 워드 등의 다중 비트들을 싱글 비트 연산 작업에서 켜고 끄거나 상호 반전시킬 수 있다.

 

비트 연산자

 

연산자	설명
&	대응되는 비트가 모두 1이면 1을 반환함. (비트 AND 연산)
|	대응되는 비트 중에서 하나라도 1이면 1을 반환함. (비트 OR 연산)
^	대응되는 비트가 서로 다르면 1을 반환함. (비트 XOR 연산)
~	비트를 1이면 0으로, 0이면 1로 반전시킴. (비트 NOT 연산)
<<	지정한 수만큼 비트들을 전부 왼쪽으로 이동시킴. (left shift 연산)
>>	부호를 유지하면서 지정한 수만큼 비트를 전부 오른쪽으로 이동시킴. (right shift 연산)

 

 

풀이

기본적으로 add, remove, check, toggle에 대해서는 아래 코드의 주석으로 달아두었다.

이외에 1~20 전체를 집합에 추가하는 all 명령어와 empty 명령어를 살펴보자.

먼저, empty 명령어는 공집합을 만들어준다. 즉, 숫자가 아무것도 존재하지 않게 해주어야 한다.

따라서, 0으로 설정하면 된다.

다음은 all 명령어다. 

all의 경우에는 1~20를 집합에 포함시켜주어야 한다. 

비트마스크의 예를 간략하게 들면, {1,2,3, 4}의 집합을 비트마스크로 표현하면 11110(2)이 된다.

-> (2^0) *0 + (2^1)*1 + ... (2^4)*1라는 표현식이 나온다. => 31

이를 시프트를 통해 편하게 표현하면, (1 << 5) -1로 표현할 수 있다.  => 31

따라서, 1부터 20까지니까 2^0+2^1+...+2^19+2^20 = 2^21 -1이기 때문에 all 은 1 << 21 -1 해주어야한다.

 

코드

 

package remindBOJ;

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

public class Set_11723 {
    final static String NEW_LINE = "\n", ALL = "all", EMPTY = "empty", ADD ="add", REMOVE ="remove", CHECK = "check", TOGGLE = "toggle";
    final static char TRUE = '1', FALSE = '0';
    final static int FULL_NUMBER = (1 << 21) -1, EMPTY_NUMBER =0;

    static int num;
    static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(br.readLine());
        num =0;
        sb  = new StringBuilder();

        while(m-- >0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            solution(st);
        }
        br.close();
        System.out.println(sb.toString());
    }

    private static void solution(StringTokenizer st) {
        String cmd = st.nextToken();
        int x = st.hasMoreTokens() ? Integer.parseInt(st.nextToken()) : EMPTY_NUMBER;

        switch (cmd) {
            case ALL:
                num = FULL_NUMBER;
                break;
            case EMPTY:
                num = EMPTY_NUMBER;
                break;
            case ADD :
                num |= (1 << x); // |(OR) 연산을 통해 해당 값을 넣어줌
                break;
            case REMOVE:
                num &= ~(1 << x); // 전체 비트를 ~(NOT) 를 통해 역으로 바꿔주고 &(AND) 연산을 통해 해당 값을 지워줌
                break;
            case CHECK:
                sb.append( (num&(1 << x)) != EMPTY_NUMBER ? TRUE : FALSE).append(NEW_LINE); // &(AND) 연산을 통해 값이 0이 아니면 TRUE를, 아니면 FALSE를 추가
                break;
            case TOGGLE:
                num ^= (1 << x); // ^(XOR) 연산(대응되는 비트가 서로 다르면 1을 반환)을 통해 있으면 제거, 없으면 추가를 해준다.
                break;
            default :
                break;
        }
    }
}

 

 

Reference

www.tcpschool.com/c/c_operator_bitwise

ko.wikipedia.org/wiki/%EB%A7%88%EC%8A%A4%ED%81%AC_(%EC%BB%B4%ED%93%A8%ED%8C%85)