[백준 4주차 - 11723] 집합 (Java)

📌 문제

 

 

📝 풀이과정

비트연산자를 활용하는 비트마스킹 문제이다

이렇게 집합을 비트로 표현할 수 있다. 

 

- add

x번째 비트가 꺼져있다면 x번째 비트 켜기

S | = (1<<x)

(x 번째 비트가 켜져있어도 x번째 비트는 켜기 때문에 x번째 비트가 꺼져있는 지 확인하지 않아도 된다)

 

- remove

x번째 비트가 켜져 있다면 x번째 비트 끄기

S &= ~(1<<x)

(x 번째 비트가 꺼져있어도 x번째 비트는 끄기 때문에 x번째 비트가 켜져있는지 확인하지 않아도 된다)

 

- check

x번째 비트가 켜져있으면 1출력, 꺼져있으면 0 출력

if (S & (1<<x)) 

 

- toggle 

x번째 비트가 켜져있으면 끄고, 꺼져있다면 켜기 (XOR연산)

S ^= (1<<x)

 

- all

1번째부터 20번째 비트까지 모두 켜기

S = (1<<n+1) -1

 

- empty

1번째부터 20번째 비트까지 모드 끄기

S=0

 

⚠️ System.out.println()을 하니 시간초과가 났다. BufferedWriter나 StringBuilder를 사용하도록 하자!

 

 

💻 코드

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

public class Main{
    public static void main(String[] args)throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		
		int x=0,n=20;
		int result=0;
		int m=Integer.parseInt(br.readLine());
		
		for(int i=0;i<m;i++){
			StringTokenizer st=new StringTokenizer(br.readLine());
			String operator=st.nextToken();
			if(!operator.equals("all") && !operator.equals("empty")){
				x=Integer.parseInt(st.nextToken());
			}
			switch(operator){
				case "add":
					result |=(1<<x); //x번째 비트 켜기
					break;
				case "remove":
					result &=~(1<<x);//x번째 비트 끄기
					break;
				case "check": 
					if((result&(1<<x))!=0) bw.write(1+"\n"); //x번째 비트 on
					else bw.write(0+"\n"); //x번째 비트 off
					break;
				case "toggle":
					result ^=(1<<x); //x번째 비트가 off이면 on, on이면 off
					break;
				case "all":
					result=(1<<n+1)-1; //1부터 20까지 모든 비트 껴기
					break;
				case "empty":
					result=0;
					break;
			}
		}
		bw.flush();
		bw.close();
		br.close();
    }
}