비트마스킹으로 BOJ 11723 해결하기 (기존코드와 리펙토링)

처음 풀었던 코드는 다음과 같다.

처음에 봤을땐, 단순 구현이라고 생각했으나 O(n^2)문제를 해결하지 않으면, 시간초과가 나는 것 같아서 비트마스킹을 쓰지 않으면 시간 초과가 나는 것 같습니다.

 

비트마스킹을 사용하면, 탐색, 삽입등에서 O(1) 로 시간을 단축할 수 있습니다.

 

틀린코드

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

public class Main {
    static ArrayList<Integer> arr = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        int M= 0;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        for(int j=0; j<M; j++){
            st = new StringTokenizer(br.readLine());
            String s = st.nextToken();
//            System.out.println("command : "+s);
            int x ;

            switch(s){
                case "add":
                    x = Integer.parseInt(st.nextToken());
                    arr.add(x);
                    break;
                case "remove":
                    x = Integer.parseInt(st.nextToken());
                    arr.remove(Integer.valueOf(x));
                    break;
                case "check":
                    x = Integer.parseInt(st.nextToken());
                    if(arr.contains(x)){
                        System.out.println("1");
                    }else{
                        System.out.println("0");
                    }
                    break;
                case "toggle":
                    x = Integer.parseInt(st.nextToken());
                    if(arr.contains(x)){
                        arr.remove(Integer.valueOf(x));
                    }else{
                        arr.add(x);
                    }
                    break;
                case "all":
                    arr.removeAll(arr);
                    for(int i=1; i<=20; i++){
                        arr.add(i);
                    }
                    break;
                case "empty":
                    arr.clear();
                    break;
            }
//        System.out.println(Arrays.toString(arr.toArray()));
        }

    }
}

 

비트마스킹 리펙토링

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

public class Main {
//    static ArrayList<Integer> arr = new ArrayList<>();
    static int arr;
    public static void main(String[] args) throws IOException {
        int M= 0;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        for(int j=0; j<M; j++){
            st = new StringTokenizer(br.readLine());
            String s = st.nextToken();
//            System.out.println("command : "+s);
            int x ;

            switch(s){
                case "add":
                    x = Integer.parseInt(st.nextToken());
//                    arr.add(x);
                    arr |= (1<<x);
                    break;
                case "remove":
                    x = Integer.parseInt(st.nextToken());
//                    arr.remove(Integer.valueOf(x));
                    arr &= ~(1<<x);
                    break;
                case "check":
                    x = Integer.parseInt(st.nextToken());
                if((arr&(1<<x)) != 0){
                        System.out.println("1");
                    }else{
                        System.out.println("0");
                    }
                    break;
                case "toggle":
                    x = Integer.parseInt(st.nextToken());
//                    if(arr.contains(x)){
//                        arr.remove(Integer.valueOf(x));
//                    }else{
//                        arr.add(x);
//                    }
                    arr ^= (1<<x);
                    break;
                case "all":
//                    arr.removeAll(arr);
//                    for(int i=1; i<=20; i++){
//                        arr.add(i);
//                    }
                    arr = (1<<21)-1;
                    break;
                case "empty":
                    arr = 0;
//                    arr.clear();
                    break;
            }
//        System.out.println(Arrays.toString(arr.toArray()));
        }

    }
}

 

문제는 28%에서 해결되지 않았다. 

곰곰히 생각을 해보니까 stringbuilder를 사용해야할 것 같아서 사용해보았다

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

public class Main {
//    static ArrayList<Integer> arr = new ArrayList<>();
    static int arr;
    public static void main(String[] args) throws IOException {
        int M= 0;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        StringBuilder sb = new StringBuilder();
        for(int j=0; j<M; j++){
            st = new StringTokenizer(br.readLine());
            String s = st.nextToken();
//            System.out.println("command : "+s);
            int x ;

            switch(s){
                case "add":
                    x = Integer.parseInt(st.nextToken());
//                    arr.add(x);
                    arr |= (1<<x);
                    break;
                case "remove":
                    x = Integer.parseInt(st.nextToken());
//                    arr.remove(Integer.valueOf(x));
                    arr &= ~(1<<x);
                    break;
                case "check":
                    x = Integer.parseInt(st.nextToken());
                if((arr&(1<<x)) != 0){
                        sb.append("1 \n");
                    }else{
                        sb.append("0 \n");
                    }
                    break;
                case "toggle":
                    x = Integer.parseInt(st.nextToken());
//                    if(arr.contains(x)){
//                        arr.remove(Integer.valueOf(x));
//                    }else{
//                        arr.add(x);
//                    }
                    arr ^= (1<<x);
                    break;
                case "all":
//                    arr.removeAll(arr);
//                    for(int i=1; i<=20; i++){
//                        arr.add(i);
//                    }
                    arr = (1<<21)-1;
                    break;
                case "empty":
                    arr = 0;
//                    arr.clear();
                    break;
            }
        }
        System.out.println(sb);

    }
}