백준[15787] - 기차가 어둠을 헤치고 은하수를

• 문제: https://www.acmicpc.net/problem/15787
• 분류: 비트마스킹
• 난이도: S2
• 소요시간: 20m
• 자아성찰:
  • •  
  • 명령 형태를 보고 긴가민가 했는데, "이미 목록에 존재하는 기록이라면 해당 기차는 은하수를 건널 수 없다." 조건에서 비트마스킹임을 확신했다.
  • 최대 10만 개의 기차에 대해서 20개의 칸을 모두 비교하는 건 시간복잡도가 용서하지 않으므로, 비트마스킹을 통해 단순히 Integer 값으로 치환해 중복 여부를 판단해 시간복잡도를 줄일 수 있었다.
  • Set<Integer>를 통해 굳이 List.contains() 메서드를 사용하지 않고 중복을 제거했다.

15787번: 기차가 어둠을 헤치고 은하수를

---

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

public class B_15787 {

    static int[] arr;
    static Set<Integer> result = new HashSet<>();
    static int N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N + 1]; // 비트마스킹을 위한 int 배열 (기차)
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            int i = Integer.parseInt(st.nextToken());
            if (t == 1) {
                int x = Integer.parseInt(st.nextToken());
                arr[i] |= (1 << (x - 1)); // x번째 비트 1로 만들기 (OR)
            } else if (t == 2) {
                int x = Integer.parseInt(st.nextToken());
                arr[i] &= ~(1 << (x - 1)); // x번째 비트 0으로 만들기 (AND, NOT)
            } else if (t == 3) {
                arr[i] &= ~(1 << 19); // 가장 왼쪽 비트 0으로 만들기 (하차, AND, NOT, SHIFT)
                arr[i] <<= 1; // 각 비트 왼쪽으로 SHIFT
            } else {
                arr[i] &= ~1; // 가장 오른쪽 비트 0으로 만들기 (하차, AND, NOT)
                arr[i] >>= 1; // 각 비트 오른쪽으로 SHIFT
            }
        }
        for (int i = 1; i <= N; i++) {
            result.add(arr[i]); // Set에 중복 제거하여 기차 저장
        }
        System.out.println(result.size());
    }
}