[JAVA06] 11723. 집합

 

11723. 집합 (S5)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1.5 초	4 MB	117387	35869	26535	29.609 %

문제

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

• add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
• remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
• check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
• toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
• all: S를 {1, 2, ..., 20} 으로 바꾼다.
• empty: S를 공집합으로 바꾼다.

입력

 

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

 

 

출력

check 연산이 주어질때마다, 결과를 출력한다.

---

summary

주어진 연산(add, remove, check, toggle, all, empty) 을 실행한다. 

 

- check 연산이 주어질때마다, 결과를 출력

 

strategy

비트연산자를 사용

 

- 20개의 비트들로 이루어져있다.

- 각 자리는 0과 1로 이루어져있다. (1이면 포함, 0이면 불포함이다.)

 

note

- 1 ≤ x ≤ 20

- M (1 ≤ M ≤ 3,000,000)

 

 

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

public class Main {

    static int M, N = 0;
    
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder answer = new StringBuilder();
        
        M = Integer.parseInt(br.readLine());

        int current = 0;
        
        for(int m = 0; m < M; m++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            String action = st.nextToken();

            switch (action) {
                case "add" :
                    N = Integer.parseInt(st.nextToken()) - 1;
                
                    if((current & (1 << N)) == 0) 
                        current |= (1 << N);
                    break;
                case "remove" :
                    N = Integer.parseInt(st.nextToken()) - 1;
                
                    if((current & (1 << N)) != 0) 
                        current &= ~(1 << N);
                    break;
                case "check" : 
                    N = Integer.parseInt(st.nextToken()) - 1;
                    if ((current & (1 << N)) != 0) {
                        answer.append(1);
                    } else {
                        answer.append(0);
                    }
                    answer.append('\n');
                    break;
                case "toggle" :
                    N = Integer.parseInt(st.nextToken()) - 1;

                    if((current & (1 << N)) == 0) current |= (1 << N);
                    else current &= ~(1 << N);
                    break;
                case "all" : current = (1 << 20) - 1; break;
                case "empty" : current = 0; break; 
            }
        }

        System.out.println(answer);
    }
}

 

문제	결과	메모리	시간	언어코드	길이
11723	맞았습니다!!	313028	1052 ms	Java 11 / 수정	1797

 

MEMO

- 비트 마스킹 if 문에서 == 0 의 반대는 == 1이 아니다. (!= 0 을 사용해야 함)

- check 말고는 if 문 필요없다 (or 이랑 and 인거지 합이 아님)

- add 와 remove 할때 조건문 안걸어도 됨.

- toggle 에서는 if/else 말고 ^= (XOR) 사용하면 됨. (다른 비트들은 변화없음)

 

- 다른 풀이법으로는 set 사용하면 된다.