[백준 *Java] - 집합(11723)

집합

11723번: 집합

 

문제

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

• add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
• remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
• check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
• toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
• all: S를 {1, 2, ..., 20} 으로 바꾼다.
• empty: S를 공집합으로 바꾼다. 

입력

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

출력

check 연산이 주어질때마다, 결과를 출력한다.

 

---

👇 접근 방식 (내 생각 정리)

응? 구현 문제인건가? 라는 생각을 하게 됐습니다.

구현 문제인데 구현도 쉬워보이는데, 왜? 정답 비율이 낮지? 알고보니 아래에 메모리 제한이 있었네요....

그냥 풀기보단,

메모리를 관리하면서 풀어야겠네요..

 

after 10 min.....

역시,,

시간 초과.. 그래도 값을 삭제하고 추가를 해주는 부분이 필요하니깐 Hash로 접근을 했지만

약간의 리팩토링이 필요한 거 같습니다. 아래는 실패 코드입니다..

---

아래는 시간초과로 실패한 코드 입니다..

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

public class Main {

    static HashSet<Integer> hs = new HashSet<>();
    public static void add(int x) {
        hs.add(x);
    }

    public static void remove(int x) {
        hs.remove(x);
    }

    public static int check(int x) {
        if(hs.contains(x)) return 1;
        else return 0;
    }

    public static void toggle(int x) {
        if(hs.contains(x)) hs.remove(x);
        else hs.add(x);
    }

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

    public static void empty() {
        hs.clear();
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int M = Integer.parseInt(br.readLine());
        while (M-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            switch (st.nextToken()) {
                case "add" :
                    add(Integer.parseInt(st.nextToken()));
                    break;

                case "remove" :
                    remove(Integer.parseInt(st.nextToken()));
                    break;

                case "check" :
                    System.out.println(check(Integer.parseInt(st.nextToken())));
                    break;

                case "toggle" :
                    toggle(Integer.parseInt(st.nextToken()));;
                    break;

                case "all" :
                    all();
                    break;

                case  "empty" :
                    empty();
                    break;
            }
        }
    }
}

 

출력이 매번 System.out.println 으로 출력하기 보단,

이 부분을 StringBuilder를 이용하여, BufferedWriter 로 버퍼에담긴 걸 다출력하는 식으로 처리했습니다.

아래는 성공한 코드입니다.

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

public class Main {

    static HashSet<Integer> hs = new HashSet<>();
    static StringBuilder sb = new StringBuilder();

    public static void add(int x) {
        hs.add(x);
    }

    public static void remove(int x) {
        hs.remove(x);
    }

    public static int check(int x) {
        if(hs.contains(x)) return 1;
        else return 0;
    }

    public static void toggle(int x) {
        if(hs.contains(x)) hs.remove(x);
        else hs.add(x);
    }

    public static void all() {
        hs = new HashSet<>(Arrays.asList(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20));
    }

    public static void empty() {
        hs.clear();
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int M = Integer.parseInt(br.readLine());
        while (M-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            switch (st.nextToken()) {
                case "add" :
                    add(Integer.parseInt(st.nextToken()));
                    break;

                case "remove" :
                    remove(Integer.parseInt(st.nextToken()));
                    break;

                case "check" :
                    sb.append(check(Integer.parseInt(st.nextToken()))).append('\n');
                    break;

                case "toggle" :
                    toggle(Integer.parseInt(st.nextToken()));;
                    break;

                case "all" :
                    all();
                    break;

                case "empty" :
                    empty();
                    break;
            }
        }
		System.out.println(sb);
    }
}

 

 

 이 아래는 비트마스크로 푼 문제입니다. 한 번 보고 비트마스크에 대해서 공부하셔도 좋을 거 같습니다.

비트마스크 풀이

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

public class Boj_11723_after {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());
        int S = 0;

        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            switch(st.nextToken()) {
                case "add" : {
                    S |= (1 << Integer.parseInt(st.nextToken()));
                    break;
                }
                case "remove" : {
                    S &= ~(1 << Integer.parseInt(st.nextToken()));
                    break;
                }
                case "check" : {
                    if((S & (1 << Integer.parseInt(st.nextToken()))) > 0) {
                        sb.append("1\n");
                    } else sb.append("0\n");
                    break;
                }
                case "toggle" : {
                    int n = Integer.parseInt(st.nextToken());
                    S ^= (1<<n);
                    break;
                }
                case "all" : {
                    S = (1 << 21) -1;
                    break;
                }
                case "empty" : {
                    S = 0;
                    break;
                }
            }
        }
        System.out.println(sb);
    }
}