백준 / BOJ / 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개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

해설

처음 문제를 봤을 때 제한 시간이 1.5초인 것을 확인하였을 때 List나 ArrayList의 add를 한다면 O(n)이 걸릴 것이기에 3000000의 연산을 수행하기엔 1.5초라는 시간이 무리가 있을 것이라 판단되어 HashSet을 이용하여 add를 O(1)의 시간복잡도로 줄여서 해결했습니다. (이 문제를 다른 분들은 비트마스킹을 통해 해결하셨는데 저는 아직 익숙하지 못하여 추후에 다른 풀이법을 올리겠습니다) 

코드

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder("");

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

    static void input() throws IOException {
        M = Integer.parseInt(br.readLine());
    }

    static void process() throws IOException{
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            String order = st.nextToken();
            if(order.equals("add")){
                set.add(Integer.parseInt(st.nextToken()));
            }else if(order.equals("remove")){
                set.remove(Integer.parseInt(st.nextToken()));
            }else if(order.equals("check")){
                int num = Integer.parseInt(st.nextToken());
                if(set.contains(num)) sb.append(1).append('\n');
                else sb.append(0).append('\n');
            } else if(order.equals("toggle")) {
                int num = Integer.parseInt(st.nextToken());
                if(set.contains(num)) set.remove(num);
                else set.add(num);
            }else if(order.equals("all")) {
                for(int j=1; j<=20; j++) set.add(j);
            }else if(order.equals("empty")) {
                set.clear();
            }
        }
        System.out.println(sb.toString());
    }

    public static void main(String[] args) throws IOException{
        input();
        process();
    }
}

 

 <출처>

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