[JAVA] 백준 15787

 

 

 

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

문제

기차에 대한 명령이 다음과 같이 주어진다.

• 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번째 자리에 사람이 앉아있었다면 그 사람은 이 명령 후에 하차한다.

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

풀이

비트 마스킹을 통해서 각 기차의 상태를 변화시키면서 진행했다.

📌 명령 수행

for(int i=0; i<M; i++){
    value = br.readLine().split(" ");

    int operation = Integer.parseInt(value[0]);
    int th = Integer.parseInt(value[1])-1;
    int seat = operation < 3 ? Integer.parseInt(value[2])-1 : 0;

    if(operation == 1){
        V[th] |= (1 << (seat));
    }else if(operation == 2){
        V[th] &= ~(1 << (seat));
    }else if (operation == 3){
        V[th] = (V[th] << 1) & ~(1 << 20);
    }else{
        V[th] = (V[th] >> 1);
    }
}

각 명령을 분기를 통해서 수행했다. 비트 마스킹을 위한 비트들은 0번 부터 19번까지 사용했다.

1. 입력으로 들어온 값만큼 shift한 후 해당 비트를 1로 설정한다.
2. 입력으로 들어온 값만큼 shift한 후 해당 비트를 0으로 설정한다.
3. 좌석에 앉은 사람들을 뒤로 한칸씩 옮긴다. 이때, 사용하지 않는 비트인 20번째 비트에 사람이 있다면 0으로 설정한다.
4. 좌석에 앉은 사람들을 앞으로 한칸씩 옮긴다. 이때 첫 번째 자리에 앉은 사람은 자동으로 삭제된다.(0번이 shift되면서 사라짐)

📌 기차에 앉은 사람의 위치가 같은 기차 찾기

int count = 0;
HashSet<Integer> set = new HashSet<>();
for(int i=0; i<V.length; i++){
    if(set.contains(V[i])) continue;
    set.add(V[i]);
    count++;
}

HashSet에 각 기차의 상태를 담으면서 이전에 지나간 기차와 같은 위치에 앉은 기차가 존재한다면 continue해주고 같은 위치인 기차가 없었다면 카운트해준다.

📌 전체 코드

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

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

        String[] value = br.readLine().split(" ");

        int N = Integer.parseInt(value[0]);
        int M = Integer.parseInt(value[1]);

        int[] V = new int[N];

        for(int i=0; i<M; i++){
            value = br.readLine().split(" ");

            int operation = Integer.parseInt(value[0]);
            int th = Integer.parseInt(value[1])-1;
            int seat = operation < 3 ? Integer.parseInt(value[2])-1 : 0;

            if(operation == 1){
                V[th] |= (1 << (seat));
            }else if(operation == 2){
                V[th] &= ~(1 << (seat));
            }else if (operation == 3){
                V[th] = (V[th] << 1) & ~(1 << 20);
            }else{
                V[th] = (V[th] >> 1);
            }
        }
        int count = 0;
        HashSet<Integer> set = new HashSet<>();
        for(int i=0; i<V.length; i++){
            if(set.contains(V[i])) continue;
            set.add(V[i]);
            count++;
        }

        System.out.println(count);
    }

}

결과