[백준] 15787 기차가 어둠을 헤치고 은하수를 - BitMask(비트마스크) JAVA

https://www.acmicpc.net/problem/15787

코드설명

BitMask(비트마스크)를 활용합니다.

 

문제를 읽다보면, k번째 앉은 사람을 k+1번째로 이동시킨다. 등등과 같은 작업들로 비트마스크의 Shifting을 이용하라는 것이구나 라는것을 알아챌 수 있습니다.

 

만약, 비트마스킹을 사용하지 않으면 어떻게 될까요?

먼저 [10^6][20] 의 공간을 사용합니다. 

메모리는 512MB 제한으로 메모리는 부족하지 않습니다.

시간복잡도의 경우는 만약 command가 3 i 가 약 M번 (10^5)가 들어왔다고 가정합니다.

만약 비트마스킹을 활용하지 않을경우 매번 배열을 오른쪽으로 직접 이동시켜야하는데 이떄의 시간복잡도는 20번입니다. (20개의 일렬좌석) 20* 10^5 로 시간복잡도는 10^6 * 2 입니다. 시간복잡도도 초과하지 않으므로 충분히 이 로직을 사용가능합니다.

 

하지만, 비트마스킹을 사용한다면, 로직이 훨씬 더 간단합니다.

모든 이동로직이 단순한 Shifting으로 처리될 수 있기 떄문입니다.

그렇기에 비트마스킹을 사용한 것이지, 일반적인 구현을 사용해도 통과할 수 있는 문제입니다.

 

문제에서 가장 핵심은, command 2 번일 것 입니다.

int num = 0b11111;
System.out.println( 0b11111 & ~(1<<2) );

만약 11111 이라는 좌석이 존재하고, 3번쨰 좌석을 제거하고 싶습니다.

이떄, mask = ~(1<<2) 로 11011 의 mask를 만들어줍니다.

그 이후에 & 연산을 해주면 3번째 좌석은 비어지게 됩니다.

만약, 아무도 그자리에 안자있지 않을경우도 이미 비어있으므로 상관없습니다.

 

두번쨰 유의사항은, 총 기차의 총 좌석개수는 20개라는 점입니다. 그러므로 아래와 같이 mask를 

mask = 0b011111111111111111111  과 같이 만들어서 & 연산해줍니다. 이렇게 되면 20개좌석만 남겠지요.

arr[trainIdx] = arr[trainIdx] << 1;
int mask = ~(1 << 20);
arr[trainIdx] = arr[trainIdx] & mask;

 

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K, B, a, b;
	static int answer = 0;
	static int[] arr;
	static HashSet<Integer> hashset = new HashSet<>();
	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());
		
//		int num = 0b11111;
//		System.out.println( 0b11111 & ~(1<<2) );
		
		arr = new int[N];
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int command = Integer.parseInt(st.nextToken());
			int trainIdx = 0;
			int seatIdx = 0;
			if(command == 1 || command == 2) {
				trainIdx = Integer.parseInt(st.nextToken()) - 1;
				seatIdx = Integer.parseInt(st.nextToken()) - 1;
			}
			else if(command == 3 || command == 4) {
				trainIdx = Integer.parseInt(st.nextToken()) - 1;
			}
			
			if(command == 1) {
				arr[trainIdx] = arr[trainIdx] | 1 << seatIdx; 
			} else if(command == 2){
				//하차시키는 방법. 1111 이 있다. 만약 3번쨰 좌석을 없애고싶다면,
				// mask를 생성하자.
				// 1. 모두 1인 mask를 하나 생성한다.
				// 2. 특정 위치에 ~(1 << seat위치) 반전시킨다.
				// 3. 기존 beatmask & mask를 하면 된다.
				int mask = ~(1 << seatIdx);
				arr[trainIdx] = arr[trainIdx] & mask;
			} else if(command == 3) {
				arr[trainIdx] = arr[trainIdx] << 1;
				int mask = ~(1 << 20);
				arr[trainIdx] = arr[trainIdx] & mask;
			} else if(command == 4) {
				arr[trainIdx] = arr[trainIdx] >> 1;
				int mask = ~(1 << 20);
				arr[trainIdx] = arr[trainIdx] & mask;
			}
			
		}
		
		for(int i=0;i<N; i++) {
			hashset.add(arr[i]);
		}
		System.out.println(hashset.size());
		
	}

}