[ BOJ ][JAVA][15787] 기차가 어둠을 헤치고 은하수를

www.acmicpc.net/problem/15787

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

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	1938	537	410	28.873%

문제

N개의 기차가 어둠을 헤치고 은하수를 건너려고 한다.

기차는 20개의 일렬로 된 좌석이 있고, 한 개의 좌석에는 한 명의 사람이 탈 수 있다.

기차의 번호를 1번부터 N번으로 매길 때, 어떠한 기차에 대하여 M개의 명령이 주어진다.

명령의 종류는 4가지로 다음과 같다.

• 1 i x : i번째 기차에(1 ≤ i ≤ N) x번째 좌석에(1 ≤ x ≤ 20) 사람을 태워라. 이미 사람이 타있다면 , 아무런 행동을 하지 않는다.
• 2 i x : i번째 기차에 x번째 좌석에 앉은 사람은 하차한다. 만약 아무도 그자리에 앉아있지 않았다면, 아무런 행동을 하지 않는다.
• 3 i : i번째 기차에 앉아있는 승객들이 모두 한칸씩 뒤로간다. k번째 앉은 사람은 k+1번째로 이동하여 앉는다. 만약 20번째 자리에 사람이 앉아있었다면 그 사람은 이 명령 후에 하차한다.
• 4 i : i번째 기차에 앉아있는 승객들이 모두 한칸씩 앞으로간다. k번째 앉은 사람은 k-1 번째 자리로 이동하여 앉는다. 만약 1번째 자리에 사람이 앉아있었다면 그 사람은 이 명령 후에 하차한다.

M번의 명령 후에 1번째 기차부터 순서대로 한 기차씩 은하수를 건너는데 조건이 있다.

기차는 순서대로 지나가며 기차가 지나갈 때 승객이 앉은 상태를 목록에 기록하며 이미 목록에 존재하는 기록이라면 해당 기차는 은하수를 건널 수 없다.

예를 들면, 다음 그림을 예로 들었을 때, 1번째 기차와 같이 승객이 앉은 상태는 기록되지 않았기 때문에 은하수를 건널 수있다. 2번째 기차와 같은 상태도 기록되지 않았기 때문에 2번째 기차도 은하수를 건널 수 있다. 3번째 기차는 1번째 기차와 승객이 앉은 상태가 같으므로 은하수를 건널 수 없다.

처음에 주어지는 기차에는 아무도 사람이 타지 않는다.

은하수를 건널 수 있는 기차의 수를 출력하시오.

입력

입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다.

출력

은하수를 건널 수 있는 기차의 수를 출력하시오.

예제 입력 1

5 5
1 1 1
1 1 2
1 2 2
1 2 3
3 1

예제 출력 1

2

코드

/*
    기차가 어둠을 헤치고 은하수를
    비트마스킹
    초기값은 0으로 두고.
    좌석은 20자리이지만 비트마스킹을 위해 21자리를 만든다.
       끝 좌석                                 첫 좌석
    0 / 0 0 0 0 0 / 0 0 0 0 0 / 0 0 0 0 0 / 0 0 0 0 0
*/
import java.io.*;
import java.util.*;
public class p15787 {
    static int n, m;
    static int[] train;
    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());
        // 1 ~ N 번째 열자, 1 ~ 20번째 자리
        // 1 << 20 : 1024 * 1024 이므로 약 백만
        train = new int[n + 1];

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int command = Integer.parseInt(st.nextToken());
            int num = Integer.parseInt(st.nextToken());

            switch (command) {
                case 1 :
                    int seat = Integer.parseInt(st.nextToken());                
                    put(num, seat);
                    break;
                case 2:
                    seat = Integer.parseInt(st.nextToken());                
                    getOff(num, seat);
                    break;
                case 3:
                    moveBack(num);
                    break;
                case 4:
                    moveForward(num);
                    break;
            }
        }

        // 은하수를 건널 수 있는 기차의 수는?
        boolean[] visit = new boolean[1 << 21];
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (!visit[train[i]]) {
                ans++;
                visit[train[i]] = true;
            }
        }
        System.out.println(ans);
    }
    static void put(int num, int seat) {
        train[num] |= (1 << seat);
    }

    static void getOff(int num, int seat) {
        train[num] &= ~(1 << seat);
    }

    static void moveBack(int num) {
        train[num] <<= 1;
        // 21 칸을 모두 밀었으므로 21번째 칸에 범위 밖의 값이 남아있으므로 그 값을 검사해서 없애야 한다.(교집합)
        // 전체 수가 21 이므로 (1 << 21) -1
        train[num] &= ((1<<21) - 1);
    }

    static void moveForward(int num) {
        train[num] >>= 1;
        // 1의 반대는 0이므로
        train[num] &= ~1;
    }
}

/* hashSet을 이용해 이동가능한 기차를 구할 수도 있다.
    HashSet<Integer> trains = new HashSet<>();
    for (int i = 1; i <= n; i++) {
        trains.add(train[i]);
    }
    System.out.println(trains.size());
*/