11723_집합 (JAVA)

11723번: 집합

 

① int형 정수 이용 (비트마스크)

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

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());
		String command = "";
		int num = 0;
		int S = 0;

		for(int i=0; i<n; i++){
			st = new StringTokenizer(br.readLine());
			command = st.nextToken();

			if(st.hasMoreTokens())
				num = Integer.parseInt(st.nextToken());


			if(command.equals("add"))
				S = S | (1<<num);

			if(command.equals("remove"))
				S = S & ~(1<<num);

			if(command.equals("check")){
				if((S&(1<<num)) != 0)
					sb.append(1).append('\n');
				else
					sb.append(0).append('\n');
			}

			if(command.equals("toggle"))
				S = S ^ (1<<num);

			if(command.equals("all"))
				S = (1<<21)-1;

			if(command.equals("empty"))
				S = 0;

		}
		System.out.print(sb);
		br.close();
	}
}

int S = 0; 으로 선언하고, 명령에 따라 S의 비트마스크를 변경하며 진행하는 방법이다.

 

int형은 4Bytes=32Bits이므로, 0000 0000 0000 0000 0000 0000 0000 0000의 꼴로 나타낼 수 있다.

오른쪽부터 2의 0승, 1승, 2승 ... 32승 까지로 나타낼 수 있으며, 입력받는 x를 x승의 위치로 이동시켜 계산한다.

 

즉, 1 = 0000 0000 0000 0000 0000 0000 0000 0001 을 x만큼 왼쪽으로 이동하는 shift연산을 이용하여 x를 표현한다.

예: x=3이면, 1<<3으로 표현한다.

    1<<3은 0000 0000 0000 0000 0000 0000 0000 1000 으로 나타낼 수 있고, 이때 1은 2의 3승에 위치하게 된다.

 

 

 

1) add x -   S | (1<<x)

                     1<<x 는 x위치가 1을 의미한다.

                     S에 x가 있다면==S의 x위치가 1이라는 의미이고, 1 OR 1 = 1

                     S에 x가 없다면==S의 x위치가 0이라는 의미이고, 0 OR 1 = 1 로 해당 표현을 통해 무조건 결과는 1이 된다.

 

2) remove x -   S & ~(1<<x)

                             1<<x는 x위치가 1을 의미한다.

                             ~(1<<x)는 x위치만 0이고, 나머지 위치는 모두 1을 의미한다.

                             S에 x가 있다면==S의 x위치가 1일 때, S & ~(1<<x)를 수행하면 - 1 & 0 = 0

                             S에 x가 없다면==S의 x위치가 0일 때, S & ~(1<<x)를 수행하면 - 0 & 0 = 0 으로 결과는 무조건 0이 된다.

 

3) check x -   S & (1<<x) 의 값에 따라 출력을 달리 한다.

                          S에 x가 있다면==S의 x위치가 1일 때, S & (1<<x)의 값은 1 -> 1 출력

                          S에 x가 없다면==S의 x위치가 0일 때, S & (1<<x)의 값은 0 -> 0 출력

 

3) toggle x -   S ^ (1<<x)

                           문제의 'S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다.'를 비트마스크로 보면,

                           'S에 x가 있으면 x를 제거하고' == S의 x위치의 값을 1->0 으로 변경하고

                           '없으면 x를 추가한다.' == S의 x위치의 값을 0->1로 변경해라. 라고 해석할 수 있다.

                           1<<x의 x위치는 1이므로,

                           S의 x위치=1 일때 (1<<x)과 연산하여 0의 결과를, S의 x위치=0 일때 (1<<x)와 연산하여 1의 결과가 나와야 한다.

                           이때 사용되는 연산은 XOR이 된다.

 

4) all -   (1<<21)-1

                1<<21 : 0000 0000 0010 0000 0000 0000 0000 0000

           -              1 : 0000 0000 0000 0000 0000 0000 0000 0001

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

                                0000 0000 0001 1111 1111 1111 1111 1110 

 

5) empty -   S=0

                        'S를 공집합으로 바꾼다.' == S=0

 

 

 

 

 

 

 

② boolean[] 배열 이용

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

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());
		String command = "";
		int num = 0;
		boolean[] S = new boolean[21]; // x범위: 1~20

		for(int i=0; i<n; i++){
			st = new StringTokenizer(br.readLine());
			command = st.nextToken();

			if(st.hasMoreTokens())
				num = Integer.parseInt(st.nextToken());


			if(command.equals("add"))
				S[num] = true;

			if(command.equals("remove"))
				S[num] = false;

			if(command.equals("check")){
				if(S[num])
					sb.append(1).append('\n');
				else
					sb.append(0).append('\n');
			}

			if(command.equals("toggle"))
				S[num] = !S[num];

			if(command.equals("all"))
				Arrays.fill(S, true);

			if(command.equals("empty"))
				Arrays.fill(S, false);

		}
		System.out.print(sb);
		br.close();
	}
}

21크기로 boolean[]배열을 선언하여, 명령에 따라 해당 위치의 값을 true/false로 변경하는 방법이다.

 

 

1) add x -   S[x] = true로 변경

 

2) remove x -   S[x] = false로 변경

 

3) check x -   S[x]=true이면 1출력 / false이면 0출력

 

3) toggle x -   S[x] = !S[x]  (true->false / false->true로 변경)

 

4) all -   S[x]의 모든 값을 true로 변경  ==  Arrays.fill(S, true);

 

5) empty -   S[x]의 모든 값을 false로 변경  ==  Arrays.fill(S, false);