[백준] 11723 : 집합 - JAVA

dev-jjun·2023년 1월 2일

boj 알고리즘

코딩테스트 준비

목록 보기

4/11

🔗 문제

BOJ 11723 : 집합

난이도 - 실버 5

알고리즘 분류 - 구현, 비트마스킹

💬 풀이

static으로 클래스 전체에서 공통으로 사용가능한 ArrayList 객체를 생성하고, 넘겨받은 명령어와 원소값을 commands() 함수에 넘겨주어 명령어 값에 따라 switch문으로 명령을 수행한다.

💻 코드

시간 초과

package Baekjoon;

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

public class _11723 {

    public static List<Integer> sets = new ArrayList<>();

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

        int N = Integer.parseInt(st.nextToken());

        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            String cmd = st.nextToken();
            if (cmd.equals("empty") || cmd.equals("all")) {
                commands(cmd);
                continue;
            }

            int x = Integer.parseInt(st.nextToken());
            commands(cmd, x);
        }

    }

    public static void myRemove(int x) {
        int idx = sets.indexOf(x);
        if (idx == -1) return;
        else {
            for (int i=0; i<sets.size(); i++) {
                if (i == idx) sets.remove(i); break;
            }
        }
    }

    public static void commands(String cmd) {
        switch (cmd) {
            case "all":
                int len = sets.size();
                for (int i=0; i<len; i++) {
                    sets.set(i, i+1);
                }
                for (int i=len; i<=20; i++) {
                    sets.add(i);
                }
                break;
            case "empty":
                sets.clear();
                break;
        }
    }

    public static void commands(String cmd, int x) {
        switch (cmd) {
            case "add":
                if (sets.isEmpty()) sets.add(x);
                else if (!sets.contains(x)) sets.add(x);
                break;
            case "remove":
                myRemove(x);
                break;
            case "check":
                if (sets.contains(x)) System.out.println(1);
                else System.out.println(0);
                break;
            case "toggle":
                if (sets.contains(x)) {
                    myRemove(x);
                }
                else sets.add(x);
                break;
        }
    }
}

수정한 버전 : 비트마스킹 이용
all 명령어에서 1~20까지의 셋팅 작업이 있는 것으로 보아 20개의 원소를 가지는 boolean 배열로 초기 셋팅을 하는 것으로 접근할 수 있다.

package Baekjoon;

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

public class _11723 {

    static StringBuilder sb = new StringBuilder();
    static int bitMask = 0;

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

        int N = Integer.parseInt(st.nextToken());

        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            String cmd = st.nextToken();
            if (cmd.equals("empty") || cmd.equals("all")) {
                commands(cmd);
                continue;
            }

            int x = Integer.parseInt(st.nextToken());
            commands(cmd, x);
        }

        bw.write(sb.toString());
        bw.close();
        br.close();

    }

    public static void commands(String cmd) {
        switch (cmd) {
            case "all":
                bitMask = ~0;  // 1~20의 모든 비트를 1로 켜준다,
                break;
            case "empty":
                bitMask = 0;  // 1~20의 모든 비트를 0으로 끈다,
                break;
        }
    }

    public static void commands(String cmd, int x) {
        switch (cmd) {
            case "add":   // ex. add 1, add 2, add 3 의 결과는 -> 111
                bitMask = bitMask | 1 << (x-1); // 1 << (x-1): x-1번 비트만 1, 나머지 비트는 0으로 만들고 | 연산으로 나머지는 원래 상태를 유지한 채 x-1번 비트를 1로 바꿔준다,
                break;
            case "remove":
                bitMask = bitMask & ~(1 << (x-1)); // 1 << (x-1): 추가 시와 동일하기 x-1번 비트를 1로 만들어주고, & 연산을 진행하여 x-1번만 0으로 바뀌고 나머지는 유지되도록 한다.
                break;
            case "check":
                sb.append(((bitMask & 1 << (x-1)) == 1 << (x-1) ? 1 : 0) + "\n");
                break;
            case "toggle":
                bitMask = bitMask ^ 1 << (x-1);  // ^ 연산을 통해 x-1번 자리의 비트를 1->0. 0->1로 바꿔준다.
                break;
    			}
			}
       }

📊 정리

Java List의 시간복잡도 (*시간초과의 원인)

ArrayList
add : O(1)
remove : O(n)
get : O(1)
Contains : O(n)
iterator.remove : O(n)

*특징
- 데이터의 추가/삭제 시, 임시 배열 생성 후 데이터 복사 -> 성능저하 大
- 데이터 검색 시, 인덱스를 이용하여 빠른 임의 접근 가능

비트 마스킹 (bit masking)

비트 마스킹이란? 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법

👍 장점

수행시간이 빠르다. 대부분의 연산을 O(1)에 구현 가능
코드가 짧다.
메모리 사용량이 적다.

📍 어려웠거나 해결하지 못한 부분

remove() 함수는 해당 인덱스에 위치한 요소를 삭제하기 위해 인덱스 값을 넘겨받을 수도 있고, 특정 요소 값을 직접 넣어서 삭제할 수도 있다. String 형이나 float 형 등의 리스트는 인덱스와 원소가 구분 가능하지만, Integer 형의 경우 remove() 함수가 넘겨받은 값을 인덱스와 요소 값 중에 어떤 것으로 해석할 지 명확하지 않아 이 부분을 해결하는 데 어려움이 있었다.

➡️ indexOf() 함수로 해당 값의 인덱스로 간접 접근
*ArrayList의 indexOf()는 인자로 전달된 객체가 리스트에 존재한다면, 해당 객체의 인덱스를 리턴하고 없으면 -1을 리턴

📍 오늘의 메모

ArrayList에서 remove 사용 시, 인덱스와 size가 변화한다.

Java의 동적 배열인 ArrayList에 대해 for문을 돌며 원소를 remove 하는 경우에 인덱스는 처음 반복문을 돌때의 길이만큼 돌게 되므로 i++ 되지만, 원소가 삭제될 때마다 size가 감소한다는 사실 또한 반영해야 한다. 따라서 remove 시에 remove(i--) 와 같이 후위연산자를 사용해야 한다.
비트 마스킹을 이용하면 집합을 쉽게 표현할 수 있다.
한 줄에 하나의 출력이 주어진 문제의 경우, StringBuilder를 이용하는 편이 더 좋다.