[11723] 집합

한 동안 졸업 작품과 다른 것들로 인해서 바빠서 알고리즘을 풀지 못했다… 이런 나를 반성하면서 다시 꾸준하게 알고리즘을 풀면서 공부해야겠다!!

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

Explain

비어있는 공집합 S가 있고, 문제에 나온 명령어가 주어졌을 때 명령어에 따라 연산을 진행한다.

입력 : 첫 줄에 수행하는 연산의 수인 M이 주어진다. (1<=M<=3,000,000)

출력 : check 연산이 주어질 때마다, 출력한다.

Key Points

간단하게 비트 마스크를 이용하여 문제를 풀어보았다. 비트 마스크를 이용하여 문제에 원하는 추가, 삭제, 검색 등을 구현할 수 있다.

문제에서 집합에 추가하는 수인 x의 범위가 1<=x<=20이다. 하지만, 비트 마스크는 0 ~ N-1 까지의 수를 저장하고 있기 때문에 문제를 풀기 위해서는 입력 받은 수 모두 1을 빼주어서 0 ~ 19 로 맞추고 문제를 풀면 된다.

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

public class BOJ11723 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		
		// 내가 배운 비트마스크는 0~N-1 까지의 수를 저장하고 있기 때문에
		// 이 문제를 풀기 위해서는 입력으로 받은 수를 모두 1을 빼주고 0~19로 만든 다음에 구현하면 된다.
		// 왜냐하면 문제에서 집합에 추가할 수 있는 x의 범위가 1~20이기 때문에 내가 배운 비트마스크의 범위인 0~N-1을 맞추기 위해서
		// 입력받은 집합에서 1씩 빼주어 0~19 사이의 범위로 맞춘다.
		
		
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int N = 20;
		int s = 0; // 처음에 비어있는 집합 생성
		int M = Integer.parseInt(bf.readLine()); // test_case
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<M;i++) {
			StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
			String command = st.nextToken();
			
			if(command.equals("add")) {
				int x = Integer.parseInt(st.nextToken());
				x--;
				s = s | (1<<x);
				
			} else if(command.equals("remove")) {
				int x = Integer.parseInt(st.nextToken());
				x--;
				s = s & ~(1<<x);
				
			} else if(command.equals("check")) {
				int x = Integer.parseInt(st.nextToken());
				x--;
				int tmp = s & (1<<x);
				if(tmp !=0) {
					sb.append("1");
					sb.append("\n");
				} else {
					sb.append("0");
					sb.append("\n");
				}
				
			} else if(command.equals("toggle")) {
				int x = Integer.parseInt(st.nextToken());
				x--;
				s = s ^ (1<<x);
			} else if(command.equals("all")) {
				s = (1<<N) - 1;
			} else if(command.equals("empty")) {
				s = 0;
			}
		}
		
		System.out.println(sb.toString());
		
	}

}