백준 157877 (기차가 어둠을 헤치고 은하수를)

문제

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

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번째 기차부터 순서대로 한 기차씩 은하수를 건너는데 조건이 있다.

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

---

명령에 따라 조건을 구현해주는것은 문제가 아니었다.

마지막에 상태를 중복없이 처리하는것이 문제 였다.

처음에는 boolean 배열을 사용해 처리하려고 했다.

하지만 배열 자체가 set에 처리가 되지 않았다.

찾아보니 비트마스킹으로 해결할 수 있었다.

참고

[알고리즘] 비트마스킹(bitmasking) 이란

 

리스트 형식이나 배열 형태의 중복을 처리하기 위해서는 비트마스킹으로 해결할 수 있다.

---

전체 코드이다.

public class Main {

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

        int n = Integer.parseInt(st.nextToken());
        int m  =Integer.parseInt(st.nextToken());

        int []train = new int[n+1];

        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int commander = Integer.parseInt(st.nextToken());
            int trainNum = Integer.parseInt(st.nextToken());
            if(commander ==1){
                int seat = Integer.parseInt(st.nextToken());
                train[trainNum] |= 1 << seat;
            }
            else if(commander ==2){
                int seat = Integer.parseInt(st.nextToken());
                train[trainNum] &= ~(1<<seat);
            }
            else if(commander ==3){
                train[trainNum] <<= 1;
                train[trainNum] &= ((1 << 21) -1);
            }
            else{
                train[trainNum] >>= 1;
                train[trainNum] &= ~1;
            }
        }

        Set<Integer>set = new HashSet<>();
        for(int i=1;i<=n;i++)
            set.add(train[i]);

        System.out.println(set.size());


    }

}