[백준알고리즘] 11723: 집합 -Java

솔직히 학교 수업에서 비트마스크 대충이나마 가르쳐주시긴 했지만

인생에 쓸모 없을줄알고 제대로 공부한 적이 없었다ㅠ____ㅠ 후회해도 늦었징 

ㅇ

오늘 비트마스크에 대해 공부했다

---------------------------------------------------------------------------

1) 비트마스크

'모든 경우를 살펴보아야 하는 경우' -> 솔직히 아직 이해안됨

' 상태를 배열에 넣어야 하는 경우 ' -> 이것도

비트연산을 사용해서 부분집합 표현

• A^B -> 다르면 1, 같으면 0

• not 연산 -> 자료형에 따라 결과가 달라질 수 있음

• shift 연산 : 1 << 1 -> 10(2)

  ex) 3 << 3 : 11000(2)

  • A<<B: A x 2^B

  • A>>B: a/2^B

  • 비트 연산은 속도가 더 빠르기 때문에, 이분 탐색 시 / 대신 >> 를 사용할 수 있다.

  • (N%2==1 ) ==(N&1): 맨 마지막 수가 1인지 아닌지만 판별

길이가 N인 이진수 : 0~N-1로 구성된 부분집합으로 나타낼 수 있음

• x가 들어있는지 알고 싶다면, S & (1<<x) -> x번째 1을 넣어서 &연산

• x를 추가하고 싶다면, S | (1<<x) -> +연산은 중복된 비트 덧셈 시 에러

• x를 제거하고 싶다면, S & ~(1<<x) -> 제거하려는 위치만 0, 나머지는 1 &연산

• x를 토글, S^(1<<x)

---------------------------------------------------------

그리고 문제,

솔직히 비트마스크가 문제가아니라 ㅋㅋㅋㅋ 아 속도랑 문제 이상하게 읽어서 애먹었다.

1. 바로바로 출력해주면 시간 초과나기 때문에 StringBuilder에 모았다가 한번에 출력해주어야하고 

2. all이랑 empty는 x변수를 입력받지 않는다 ㅋㅋㅋㅋㅋㅋ

3. 그리고 1부터 20까지니까 2^0+2^1+...+2^19+2^20 = 2^21 -1이기 때문에 all 은 1>>21 -1 해주어야한다.

import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);
		StringBuilder result=new StringBuilder();
		int T=scan.nextInt();
		int S=0;
		for(int i=0; i<T; i++){
			String command=scan.next();
			if(command.equals("add")){
				int x=scan.nextInt();
				S=S|(1<<x);
			}
			else if(command.equals("remove")){
				int x=scan.nextInt();
				S=S&~(1<<x);
			}
			else if(command.equals("check")){
				int x=scan.nextInt();
				if((S&(1<<x))>0) result.append("1\n");
				else result.append("0\n");
			}
			else if(command.equals("toggle")){
				int x=scan.nextInt();
				S=S^(1<<x);
			}
			else if(command.equals("all")){
				S=(1<<21) -1;
			}
			else
				S=0;
		}
		System.out.println(result);

	}

}