[백준 스터디 2주차] 15787 기차가 어둠을 헤치고 은하수를 실버2 - 자바(Java) / 비트마스킹

📑 문제

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

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

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

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

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

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

 

입력

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

 

출력

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

 

 

 

 

 

 

 

✒️ 풀이

 좌석의 위치가 1부터 시작하므로, 편한 인덱스 접근을 위해 x번째 좌석은 (1<<x)로 판별한다.

 즉 21개의 자리수에서 0번째(이진수 맨 오른쪽)을 버리고 1번째부터 20번째까지 20개를 보는 것이다.

 

 사람을 특정 위치에 태우는건 그 위치에서 |연산, 특정 위치에서 내리는건 &연산을 하면 된다.

 한 칸씩 앞으로 가거나 뒤로 가는 것은 쉬프트(<<, >>) 연산을 사용한다.

 문제는 맨 끝에 위치한 사람들이다.   

 

✔️ 뒤로 가는 경우

◻️ 21번째에 위치한 사람은 22번째로 밀리게 된다. 

◻️ (1<<21)은 1을 22번째 자리로 미는 것이다. 여기서 1을 뺀 (1<<21)-1은 1이 21개 모여있는 이진수가 된다.

◻️ 따라서 두 이진수를 & 처리하면, 22번째에 있는 사람은 사라지게 된다.

 

✔️ 앞으로 가는 경우

◻️ 1번째에 있던 사람은 좌석으로 치지 않는 0번째로 밀리게 된다.

◻️ ~1: 11111111111111111111111111111110 (32자리)

◻️ 앞으로 민 다음 ~1과 &연산을 해주면, 계산에서 제외되어야 하는 0번째 사람은 사라진다.

 

 

 

 

 

 

🙋‍♀️ 의견

 비트마스킹 다시 해보자고 고른 문제....여전히 싫다. 컴퓨터공학이지만 수학이 싫어서 어쩌지.

 

 

 

 

 

 

 

💻 소스코드: 자바(Java)

/** https://www.acmicpc.net/problem/15787 */
public class Main_백준_15787_기차가어둠을헤치고은하수를_실버2 {

	/*ss
	 끝좌석(1<<20)				첫좌석(1<<1)
	 0 0 0 0 0 0 0 0 	....   0         0
	20번째 					1번째
	*/
	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[] trains = new int[N+1];
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int op = Integer.parseInt(st.nextToken());
			int tNum = Integer.parseInt(st.nextToken());
			int sNum = 0;
			
			switch(op) {
			case 1: // 사람을 태운다
				sNum = Integer.parseInt(st.nextToken());
				trains[tNum] |= (1<<sNum);
				break;
			case 2: // 하차한다
				sNum = Integer.parseInt(st.nextToken());
				trains[tNum] &= ~(1<<sNum);
				break;
			case 3: // 한칸씩 뒤로
				trains[tNum] <<= 1;
				//맨 왼쪽(21번째) 비트를 지워줘야 하니까
				//맨 왼쪽은 0, 20번째~1번째는 모두 1로 두고 &연산 
				trains[tNum] &= ((1<<21)-1);
				break;
			case 4: // 한칸씩 앞으로
				trains[tNum] >>= 1;
				trains[tNum] &= ~1;
			}
		}
		
		Set<Integer> set = new HashSet<>();
		for (int i = 1; i <= N; i++) {
			set.add(trains[i]);
		}
		System.out.println(set.size());
	}//end of main
	
}//end of class

 

 

 

 

 

 

 

 

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

𝘛𝘩𝘢𝘯𝘬𝘴 𝘧𝘰𝘳 𝘳𝘦𝘢𝘥𝘪𝘯𝘨