집합 - Set 구현하기

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

1. 개요

Set 라이브러리에 있는 삽입 삭제 등의 기능을 구현하는 문제입니다.

왠지 Set 를 사용하면 반칙인 것 같지만

굳이 다른 자료형을 이용하라고 낸 문제는 아닌 것 같아서 그냥 Set를 썼습니다.

2. 고난과 역경

구현 자체는 어렵지 않으나 관건은 시간 제한입니다.

보통 출력하면 생각나는 System.out.print 가 문제였습니다.

출력값을 어디에 저장해뒀다가 한꺼번에 출력을 할 필요가 있어 보였고

BufferedWriter로 바꿨더니 통과할 수 있었습니다.

3. 대안

문제상에서 입력 원소 값의 범위가 정해져 있기 때문에

2진수의 비트연산을 이용해서 조금 더 간단하게 해결할 수 있습니다.

10	9	8	7	6	5	4	3	2	1	0
0	0	0	0	0	0	0	0	0	0	0

S이라는 변수에 0이 저장되어있습니다.

add 3이라는 명령이 들어오면  S = S | 1 << 3 ;  을 실행합니다.

즉, 00..001  1  을 옆으로  <<  3칸  3  밀어서 00..001000으로 만들고

이것과 기존의 S 를 OR  |  하면 

10	9	8	7	6	5	4	3	2	1	0
0	0	0	0	0	0	0	1	0	0	0

3이라는 원소가 하나 들어있다는 의미를 나타내는 S를 얻게 됩니다.

 

4. 소스코드

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

class Main {
    public static void main(String[] args) throws IOException {
    	
    	BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	int m = Integer.parseInt(bf.readLine());

    	Set<Integer> S = new HashSet<Integer>();

    	while(m>0) {
    		String l = bf.readLine();
    		String[] command = l.split(" ");
    		int x=0;
    		if(command.length > 1) x = Integer.parseInt(command[1]);
    		
    		if(command[0].equals("add")) {
    			S.add(x);
    		}
    		else if(command[0].equals("remove")) {
    			S.remove(x);
    		}
    		else if(command[0].equals("check")) {
     			bw.write(check(S, x)+"\n");     			
    		}
    		else if(command[0].equals("toggle")) {
    			if(S.contains(x)) S.remove(x);
    			else S.add(x);
    		}
    		else if(command[0].equals("all")) {
    			Integer[] allnum = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
    			S = new HashSet<Integer>(Arrays.asList(allnum));
    		}
    		else if(command[0].equals("empty")) S.clear();
    		    		
    		m--;
    	}
    	
    	bw.flush();
    	bw.close();
    	
    	
    }
    public static int check(Set<Integer> s, int x) {
    	
    	if(s.isEmpty()) return 0;
    	for(Integer a : s) {
    		if(a==x) {
    			return 1;
    		}  			
    	}
    	return 0;
    }
}