[JAVA] O(1) 성능으로 집합을 다루기 (비트 마스크, 배열) - 백준 11723번

백준

11723번 - '집합'

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

---

접근

• 클래스의 인스턴스와 메서드로 집합, add, remove, check, toggle, all, empty구현
• 집합 ArrayList S
• 집합에 해당 값이 삽입되어 있는지 확인할 isContains 배열
• switch case 구문으로 입력받은 값 처리.

import java.util.*;
import java.io.*;
public class Solve11723 {
    public static class Command{
        private List<Integer> S;
        private boolean isContains[];

        public Command(){
            S = new ArrayList<>(20);
            isContains = new boolean[21]; //1~20까지 해당 수가 이미 포함됐는지 확인하는 배열
            Arrays.fill(isContains, false);
        }
        //해당 값이 List에 포함되어 있는지 확인하는 함수
        public boolean containCheck(int num){
            if(isContains[num]) return true;
            else return false;
        }
        public void add(int num){
            S.add(num);
            isContains[num] = true;
        }
        public void remove(int num){
            S.remove(S.indexOf(num));
            isContains[num] = false;
        }
        public int check(int num){
            if(isContains[num]) return 1;
            else return 0;
        }
        public void toggle(int num){
            if(isContains[num]) {
                remove(num);
                isContains[num] = false;
            }
            else {
                add(num);
                isContains[num] = true;
            }
        }
        public void all(){
            empty();
            for(int i = 1; i <= 20; i++){
                S.add(i);
            }
            Arrays.fill(isContains, true);
        }
        public void empty(){
            S.clear();
            Arrays.fill(isContains, false);
        }
    }

    public static void main(String [] args) throws IOException{
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Scanner sc = new Scanner(System.in);
        //수행해야 하는 연산 수 M
        int testCase = sc.nextInt();
        Command c = new Command();

        //M만큼 입력 받기.
        for(int i = 0; i < testCase; i++){
            String command = sc.next();
            //switch case로 문자열 분류
            int num;
            switch(command){
                case "add":
                    num = sc.nextInt();
                    if(!c.containCheck(num)) c.add(num);
                    break;
                case "check":
                    num = sc.nextInt();
                    bw.write(c.check(num) + "\n");
                    bw.flush();
                    break;
                case "remove":
                    num = sc.nextInt();
                    if(c.containCheck(num)) c.remove(num);
                    break;
                case "toggle":
                    num = sc.nextInt();
                    c.toggle(num);
                    break;
                case "all":
                    c.all();
                    break;
                case "empty":
                    c.empty();
                    break;
            }
        }
        bw.close();
    }
}

결과

시간초과

반례는 없었지만, 시간초과가 발생했다.

---

시간초과 발생 원인

1. List S 사용으로 인한 비효율적인 연산이 발생했다.

• add(num)연산은 O(1)이지만,
• remove(num) 은 `indexOf(num)` 연산을 통해 먼저 탐색한 후 제거하므로, O(n)의 시간이 걸린다.
• 특히 `S.remove(S.indexOf(num))` 최악의 경우 집합 S 전체를 검색하므로 성능이 매우 나쁜 방식이다.

2. List를 굳이 유지할 필요가 없다.

• 이미 `boolean isContains[21]` 배열을 통해 집합의 상태를 관리하고 있기 때문이다.
• 근데 추가로 `List<Integer> S`도 따로 관리해야하니 이중 자료구조로 낭비가 발생한 것이다.

---

개선된 코드

2가지 방법이 있다.

 

1. boolean[]만 사용하는 방법

import java.util.*;
import java.io.*;
public class Solve11723 {
    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int testCase = sc.nextInt();
        boolean[] S = new boolean[21]; // 1~20 인덱스 사용

        for (int i = 0; i < testCase; i++) {
            String command = sc.next();
            int num = 0;
            if (!command.equals("all") && !command.equals("empty")) {
                num = sc.nextInt();
            }

            switch (command) {
                case "add":
                    S[num] = true;
                    break;
                case "remove":
                    S[num] = false;
                    break;
                case "check":
                    bw.write(S[num] ? "1\n" : "0\n");
                    bw.flush();
                    break;
                case "toggle":
                    S[num] = !S[num];
                    break;
                case "all":
                    Arrays.fill(S, true);
                    break;
                case "empty":
                    Arrays.fill(S, false);
                    break;
            }
        }
        bw.close();
    }
}

• toggle은 기존 값이 true면 false로, 기존 값이 false면 true로 바꾸는 것이기 때문에 논리 부정연산자(!)로 구현했다.

 

 

2. 비트마스크 사용

비트마스크란?

• 정수의 각 비트를 집합의 원소로 생각해서,
• n번째 비트가 1이면, n이 집합에 포함된 것으로 간주하는 방식이다.

비트마스크에 대한 자세한 설명은 추후 포스팅.

import java.io.*;
import java.util.*;

public class Solve11723 {
    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);
        BufferedWriter  bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int M = sc.nextInt();
        int S = 0; // 집합을 비트로 표현

        for (int i = 0; i < M; i++) {
            String command = sc.next();
            int num = 0;
            if (!command.equals("all") && !command.equals("empty")) {
                num = sc.nextInt();
            }

            switch (command) {
                case "add":
                    S |= (1 << num);
                    break;
                case "remove":
                    S &= ~(1 << num); //num번째 비트를 0으로 바꿈 ~(NOT)
                    break;
                case "check":
                    bw.write(((S & (1 << num)) != 0 ? "1\n" : "0\n")); //num번째 비트가 0인지 판별
                    bw.flush();
                    break;
                case "toggle":
                    S ^= (1 << num); //num번째 비트를 반대로 바꿈. ^(XOR)
                    break;
                case "all":
                    S = (1 << 21) - 1; // 1~20을 모두 켜기
                    break;
                case "empty":
                    S = 0;
                    break;
            }
        }
        bw.close();
    }
}

 

1 << num 인 이유?

• 1을 이진수로 표현한 값은 000...0001 인데,
• 0번째 비트인 가장 오른쪽 비트 1을 왼쪽으로 num만큼 밀면서 검사하거나 바꿀 수 있기 때문이다.
• 기준이 0이면 무조건 0이기 때문에, 아무 비트도 선택할 수 없게 된다.
• 즉, 1을 옮겨서 원하는 위치를 조작해야하기 때문.