구현 - BOJ 11723 집합

HashSet 을 사용한 구현코드

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

public class BOJ11723 {

    static HashSet<Integer> set = new HashSet<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int k = Integer.parseInt(st.nextToken());
        for(int i = 0 ; i < k ; i ++){
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            int num = Integer.parseInt(st.nextToken());
            switch(str){
                case "add" :
                    add(num);
                    break;
                case "check" :
                    check(num);
                    break;
                case "toggle" :
                    toggle(num);
                    break;
                case "all" :
                    all();
                    break;
                case "empty" :
                    empty();
                    break;
                case "remove" :
                    remove(num);
                    break;
            }
        }
    }

    static  void add(Integer num){
        set.add(num);
    }

    static void check(Integer num){

        if(set.contains(num)){
            System.out.println(1);
        }else{
            System.out.println(0);
        }
    }
    static void empty(){
        set.clear();
    }

    static void toggle(int num){
        if(set.contains(num)){
            set.remove(num);
        }else{
            set.add(num);
        }
    }

    static void all(){
        for(int i = 1 ; i <=20; i ++){
            set.add(i);
        }
    }

    static void remove(int num){
        set.remove(num);
    }
}

---

처음 문제를 보았을 때 HashSet을 사용하여 풀면 될 것 같다고 생각했다.

하지만 결과는 시간초과

HashSet 을 사용하지 않고 어떻게 더 효율적으로 문제를 풀 수 있을 까 생각을 해보았지만.... 결국 답을 찾지 못하고 문제를 푼 사람들에게 힌트를 얻기로 했다.

대부분의 사람들이 bitmask : 정수의 이진수 표현을 자료구조로 쓰는 기법 으로 문제를 풀었다.
이진 숫자로 0, 1 값을 가질 수 있고 이에 따라 true/false, on/off 와 같은 상태를 나타내는 것이 가능하다.

글로 읽으면 그래서 0과 1로 어떻게 사용하는거지 ? 생각이 들 수 있다.
결론을 이야기 하자면 만약 최대 숫자가 이고 1 3 5 이렇게 집합에 들어있다면
10101 로 나타내자는 것이다. 즉 0과 1을 사용하여 값을 가지고 있는지 없는지를 판단한다.
또한 & ,| ,~, ^ 연산을 사용하고 >>, << 도 사용하여 문제를 풀면된다.

구현소스는 다음과 같다

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int S = 0;
        int M = Integer.parseInt(br.readLine());
        StringTokenizer st;
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            if(str.equals("all")) S = (1 << 21) - 1;
            else if(str.equals("empty")) S = 0;
            else {
                int num = Integer.parseInt(st.nextToken());
                if(str.equals("add"))
                    S |= (1 << num);
                else if(str.equals("remove"))
                    S &= ~(1 << num);
                else if(str.equals("check"))
                    sb.append((S & (1 << num)) != 0 ? 1 : 0).append("\n");
                else if(str.equals("toggle"))
                    S ^= (1 << num);
            }
        }
        System.out.println(sb);
    }
}

참고 블로그 : https://myeongju00.tistory.com/30