의욕이 넘치는 날!!🔥

문제링크

백준 #11723. 집합

풀이방법

메모리가 4mb다 ㅋㅋ... 모.. array나 linkedList로는 해결할 수 없는 문제인걸 알 수 있죠??

그래서 비트마스킹을 사용했습니다! 비트마스킹은 비트단위로 값을 보존하고, 그걸 이용하는 거죠~ 1 ~ 20 사이의 수만 사용하기 때문에 int 타입(최대 32비트)으로 충분히 비트 값을 보존할 수 있습니다. 각 연산을 비트로 계산하는건 다음과 같습니다.

• add: or, << 연산 / num만큼 비트를 이동시키고 or 연산을 하면 해당 비트를 1로 만들 수 있습니다.
• remove: and, <<, not / num만큼 bit를 이동시키고, 비트를 반전시켜 and 연산을 하면 다른 비트들은 영향을 받지 않고 해당 비트 값만 0으로 만들 수 있습니다.
• check: and, << 연산 / num만큼 비트를 이동시키고, and 연산을 해 그 결과가 0보다 크면 해당 비트가 1이였다는 뜻이죠!
• toggle: xor, << 연산 / num만큼 비트를 이동시키고, xor연산을 하면 다른 비트들은 1^0=1, 0^0=0이어서 영향을 받지 않고, 해당 비트는 1^1=0, 0^1=1이기 때문에 전환할 수 있죠!
• all: or, not 연산 / 생략
• empty: and 연산 / 생략

+) 비트마스킹 관련 정리한 글
알고리즘 > 비트마스킹(Bit Masking)

코드

import java.util.Scanner;

public class Set {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int m = Integer.parseInt(sc.nextLine());
        String op;
        String[] splitOp;
        int bits = 0;

        StringBuilder result = new StringBuilder();

        while ((--m) >= 0) {
            op = sc.nextLine();
            splitOp = op.split(" ");

            if (splitOp[0].equals("add")) {
                bits |= (1 << Integer.parseInt(splitOp[1]));
            } else if (splitOp[0].equals("remove")) {
                bits &= ~(1 << Integer.parseInt(splitOp[1]));
            } else if (splitOp[0].equals("check")) {
                if ((bits & (1 << Integer.parseInt(splitOp[1]))) > 0) result.append("1\n");
                else result.append("0\n");
            } else if (splitOp[0].equals("toggle")) {
                bits ^= (1 << Integer.parseInt(splitOp[1]));
            } else if (splitOp[0].equals("all")) {
                bits |= ~(0);
            } else { // splitOp[0] == "empty"
                bits &= 0;
            }
        }

        System.out.print(result.toString());
    }
}

입력된 연산자에 따라 다른 연산을 진행하기 위해 if-else 문을 사용했는데요, 팩토리 메서드 패턴과 다형성을 이용하면 좋은 연습이 될 수 있겠네요! 나중에 관련 글 진행하면서 해보도록하겠습니다 ~_~

🙇🏻‍♀️