[비트마스킹, set] 백준 11723번 집합 c++, java 풀이

BOJ 11723번 집합 c++ 및 java 풀이

• 난이도: 실버5
• 백준 11723번 집합
  
  
  

문제 정리

비어 있는 공집합 S가 주어졌을때 다음 연산을 수행하는 프로그램을 작성하시오

1. add x : S에 x를 추가한다. (1 <= x <= 20) S에 이미 x가 있는 경우 연산 무시
2. remove x : S에서 x를 제거한다. S에 x가 없는 경우 무시
3. check x : S에 x가 있으면 1, 없으면 0을 출력
4. toggle x : S에 x가 있으면 x를 제거, 없으면 x를 추가
5. all: S를 {1,2,...20}으로 바꾼다.
6. empty: S를 공집합으로 바꾼다.
7. 수행해야하는 연산은 최대 3,000,000개 이다.
8. check 연산이 있을때마다 결과를 출력한다.
   
   
   

문제 접근

총 3가지 방법으로 풀어보았습니다.

1. 배열을 이용한 풀이
   수가 1부터 20까지 있으므로 각 수가 있는지 없는지 표시할 배열을 생성하여 0이면 집합에 값이 없음, 1이면 집합에 값이 있음으로 하여 표현하였습니다.
2. 비트마스킹
   shift 연산을 통해 비트 마스킹을 했습니다.
   숫자 2가 있다면 010으로 집합에 2가 있음을 2번째 비트를 1로 하여 표현하였습니다.
3. set을 이용한 풀이
   가장 단순한 풀이 입니다. add 하면 set에 실제 넣고, remove 하면 실제 set에서 삭제합니다.
   제일 처음 naive하게 set 자료구조를 이용해 풀었습니다.
   하지만 시간초과가 발생하여 다른 풀이로 풀어보게 되었습니다.
   하지만 알고보니.. 출력이 너무 많아서 그때 마다 System.out.println으로 해서 시간초과가 난것이 었습니다 ㅠㅠ
   출력이 3백만개 까지 있을 수 있는데 그것을 간과했습니다...
   java는 BufferedWriter나 StringBuilder를 이용하면 간단히 해결 가능합니다.
   
   
   

비트 마스킹 문제 풀이

배열과 set을 이용한 풀이는 간단하니 비트 마스킹 풀이를 설명하겠습니다.

1. add를 한다면 몇 번째 bit를 검사할지 check 변수를 만듭니다. 이는 1 << (num - 1) 로 표현합니다.
   1 << 0 이 1과 같기 때문에 (num-1)만큼 shift 해야 합니다.
2. add의 경우 check와 OR 연산을 하면 해당 bit를 1로 변경할 수 있습니다.
3. remove의 경우 ~연산을 통해 모든 bit를 반전시키고 &연산을 하면 해당 비트만 0으로 만들 수 있습니다.
   예를들어 2번째 비트면 010 입니다. ~연산을 하면 101입니다.
   여기에 &연산을 하면 해당 비트 빼고는 모두 1이니까 &연산을 하면 다른 비트는 그대로이고 2번째 비트만 0이 됩니다.
4. all연산은 20 비트 왼쪽으로 이동시키고 1을 빼며 20개의 비트가1인 상태가 됩니다.
5. empty는 그냥 0으로 바꾸어주면 됩니다.
   
   
   

백준 11723번 집합 c++ 코드

백준 11723번 집합 java 코드

 

그외 풀이

1. 배열

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

class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb =new StringBuilder();
		int M = Integer.parseInt(br.readLine());
		int[] set = new int[21];

		int num = 0;
		for(int i=0; i<M; i++){
			String[] temp = br.readLine().split(" ");
			if(!temp[0].equals("empty") && !temp[0].equals("all"))
				num = Integer.parseInt(temp[1]);
			switch(temp[0]){
				case "add":
					set[num] = 1;
					break;
				case "remove":
					set[num] = 0;
					break;
				case "check":
					if(set[num] == 1)
						sb.append(1 + "\n");
					else
						sb.append(0 + "\n");
					break;
				case "toggle":
					if(set[num] == 1)
						set[num] = 0;
					else
						set[num] = 1;
					break;
				case "all":
					for(int j=1; j<=20; j++)
						set[j] = 1;
					break;
				case "empty":
					for(int j=1; j<=20; j++)
						set[j] = 0;
					break;
			}
		}
        System.out.println(sb);
		br.close();
	}

}

 

2. set 이용

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

class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
		int M = Integer.parseInt(br.readLine());
		HashSet<Integer> set = new HashSet<>();
		HashSet<Integer> set2 = new HashSet<>();

		for(int i=1; i<=20; i++)
			set2.add(i);

		int num = 0;
		for(int i=0; i<M; i++){
			String[] temp = br.readLine().split(" ");
			if(!temp[0].equals("empty") && !temp[0].equals("all"))
				num = Integer.parseInt(temp[1]);
			switch(temp[0]){
				case "add":
					set.add(num);
					break;
				case "remove":
					set.remove(num);
					break;
				case "check":
					if(set.contains(num))
						sb.append(1 + "\n");
					else
						sb.append(0 + "\n");
					break;
				case "toggle":
					if(set.contains(num))
						set.remove(num);
					else
						set.add(num);
					break;
				case "all":
					set = new HashSet<>(set2);
					break;
				case "empty":
					set.clear();
					break;
			}
		}
        System.out.println(sb);
		br.close();
	}

}

 

배운 점

1. cpp에서 endl로 개행을 하면 느리다. "\n"을 사용하자

2. java에서 출력이 많다면 bw나 sb를 이용하자

3. 비트마스킹을 이용해 특정 비트를 켜고 끄는 법

4. cpp에서 switch문에 string 사용하는 방법

 

인증

시간초과 정말 많이도 나왔네요 ㅋㅋㅋㅋㅋ

그놈의 출력때문에.. ㅠㅠ

c++도 endl로 하면 느리대서 해보니까 바로 시간초과 났어요(맨 위에 시간초과 난 코드)

풀이가 잘못된 줄알고 풀이만 3가지로 풀어봤네요 ㅋㅋㅋㅋㅋ