[백준] 11723번 : 집합 - JAVA

백준 11723

 

 

개요

위 문제는 최대 연산의 수(M)가 3,000,000이기 때문에 반복문을 사용하면 안될 것 같아 HashMap 자료구조를 사용하여 문제를 해결하였다.

 

해당 문제를 해결한 후 다른 사람들이 어떤 방식으로 풀었는지 확인할 결과 비트마스크 알고리즘을 사용하여 푼 방식이 존재하여 필자는 아래 2가지 방법으로 문제를 풀어보았다.

 

성공소스

1. HashMap 사용

• add: map의 containsKey와 put 메서드를 사용하여 x값을 추가한다.
• remove: map의 remove 메서드를 사용하여 x값을 제거한다.
• toggle: map의 containsKey 메서드와 put, remove 메서드를 활용한다.
• all: 반복문을 사용하여 1 ~ 20을 map에 put한다.
• empty: map의 clear 메서드를 사용한다.

참고로 향상된 switch 문은 JDK 14버전부터 사용이 가능한데 백준에 소스를 제출할 때는 JDK 11버전까지 밖에 없어 사용할 수 없다.

 

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        final int SET_SIZE = 20;

        int m = Integer.parseInt(br.readLine());
        Map<Integer, Integer> S = new HashMap<>();

        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());
            String oper = st.nextToken();

            int x = 0;
            if(!oper.equals("empty") && !oper.equals("all")) {
                x = Integer.parseInt(st.nextToken());
            }

            switch (oper) {
                case "add":
                    if (!S.containsKey(x)) {
                        S.put(x, x);
                    }
                    
                    break;
                case "remove":
                    S.remove(x);
                    break;
                case "check":
                    if (S.containsKey(x)) {
                        sb.append(1);
                    } else {
                        sb.append(0);
                    }

                    sb.append("\n");
                    break;
                case "toggle":
                    if (S.containsKey(x)) {
                        S.remove(x);
                    } else {
                        S.put(x, x);
                    }
                    
                    break;
                case "all":
                    S.clear();

                    // 1 ~ 20 삽입
                    for (int i = 0; i < SET_SIZE; i++) {
                        S.put(i + 1, i + 1);
                    }
                    
                    break;
                case "empty":
                    S.clear();
                    break;
                default:
                    throw new IllegalStateException("Unexpected value: " + oper);
            }
        }

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

}

 

 

 

2. 비트마스크 사용

비트마스크(bit mask)란 이진수를 활용한 알고리즘 또는 문제해결 기술 중의 하나로 집합과 관련된 알고리즘 문제를 풀 때 많이 사용한다고 한다.

 

이진수는 0과 1만 존재하며 1은 on, 0은 off로 사용한다. 

 

비트 연산자란

숫자 8(a)의 경우 이진수로는 0b1000.

숫자 12(b)의 경우 이진수로는 0b1100.

 

1. AND: 이진수 자릿수가 둘 다 1인경우 1(true).

  연산자: &

   ex) a & b => 0b1000 => 8

 

2. OR: 이진수 자릿수가 하나라도 1인 경우 1.

  연산자: |

   ex) a | b => 0b1100 => 12

 

3. XOR: 이진수 자릿수가 같지 않은 경우 1.

  연산자: ^

   ex) a ^ b => 0b0100 => 4

 

4. NOT: 이진수(0 또는 1) 반전.

  연산자: ~

   ex) ~a => 0b0111 ( 1111 0111 )=>  -9

 

# ~8이 -9가 되는 이유는 컴퓨터에서 음수를 표현할 때, 2의 보수 방식으로 표현하기 때문이다.

이진수 1111 0111은 8비트에서 음수를 표현하는 2의 보수 표현으로 2의 보수는 1의 보수(bit 반전)를 구하고 1을 더하는 과정으로 구할 수 있다.
그러므로 1111 0111의 1의 보수는 0000 1000이며 여기에 1을 더하면 0000 1001이 되어 9가 되고 음수이므로 -9이다.
결론적으로 ~8의 결과는 이진수로 1111 0111이고 이는 10진수로 -9이다. 

 

5. 시프트 연산자의 경우 아래 링크를 참고하면 된다.

 

https://jiji-gilog.tistory.com/7

[백준] 1920번 : 수 찾기 - JAVA

 

 

public class Main {

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

        // 공집합
        int set = 0;
        int m = Integer.parseInt(br.readLine());

        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());
            String oper = st.nextToken();

            int x = 0;
            if(!oper.equals("empty") && !oper.equals("all")) {
                x = Integer.parseInt(st.nextToken());
            }

            switch (oper) {
                case "add":
                    // x가 3인 경우, 0b1000 (2^3)
                    set |= 1 << x;
                    break;
                case "remove":
                    // x가 3인 경우, 0b0000 &= 0b0111 => 0b0000
                    set &= ~(1 << x);
                    break;
                case "check":
                    sb.append((set & 1 << x) != 0 ? 1 : 0).append("\n");
                    break;
                case "toggle":
                    // x가 3인 경우, 0b1100 ^= 0b1000 => 0b0100
                    set ^= (1 << x);
                    break;
                case "all":
                    set = (1 << 21) - 1;
                    break;
                case "empty":
                    set = 0;
                    break;
                default:
                    throw new IllegalStateException("Unexpected value: " + oper);
            }
        }

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

}