백준 15787 - 기차가 어둠을 헤치고 은하수를

Java

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

문제

접근 방법

기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)는 보기와 같이 100000으로 큰 숫자이다.
따라서, 최대한 O(n)으로 해결하기 위해 2차원 배열을 이용해 기차를 나타내었고 기차 중복은 Set을 이용하여 중복이 되지 않은 기차의 수를 세어 해결하였다.

코드

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

public class Main {
	static int n, m, result;
	static int[][] train;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());

    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());

    	train = new int[n + 1][20];
    	int order, tidx, idx;
    	while(m-- != 0) {
    		stk = new StringTokenizer(br.readLine());
    		order = stoi(stk.nextToken());
    		if(order == 1 || order == 2) {
    			tidx = stoi(stk.nextToken());
    			idx = stoi(stk.nextToken()) - 1;
    			if(order == 1)
    				train[tidx][idx] = 1;		// 좌석 추가
    			else
    				train[tidx][idx] = 0;		// 좌석 제거
    		}
    		else {
    			tidx = stoi(stk.nextToken());
    			if(order == 3)
    				back(tidx);		// 좌석 뒤로 이동
    			else
    				front(tidx);	// 좌석 앞으로 이동
    		}
    	}

    	Set<String> set = new HashSet<>();

    	for(int i = 1; i < n + 1; i++) {
    		set.add(Arrays.toString(train[i]));			// set으로 중복 제거
    	}

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

    	br.close();
	}

	static void front(int tidx) {
		for(int i = 0; i < 19; i++) {
			train[tidx][i] = train[tidx][i + 1];
		}
		train[tidx][19] = 0;
	}

	static void back(int tidx) {
		for(int i = 19; i > 0; i--) {
			train[tidx][i] = train[tidx][i - 1];
		}
		train[tidx][0] = 0;
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

비트 마스킹으로 해결

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

public class Main {
	static int n, m, result;
	static int[] train;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());

    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());

    	train = new int[n + 1];
    	int order, tidx, idx;
    	while(m-- != 0) {
    		stk = new StringTokenizer(br.readLine());
    		order = stoi(stk.nextToken());
    		if(order == 1 || order == 2) {
    			tidx = stoi(stk.nextToken());
    			idx = stoi(stk.nextToken()) - 1;
    			if(order == 1) {
    				train[tidx] |= 1 << idx;		// 해당하는 좌석 등록
    			}
    			else {
    				train[tidx] &= ~(1 << idx);		// 해당하는 좌석 삭제
    			}
    		}
    		else {
    			tidx = stoi(stk.nextToken());
    			if(order == 3) {
    				train[tidx] = train[tidx] << 1;	// 모든 좌석을 뒤로 한 칸씩 보낸다.
    				train[tidx] &= (1 << 20) - 1;	// 뒤로 보내면 20번째 bit가 생기므로 0 ~ 19 까지 비트를 1과 & 해주어 없애준다.
    			}
    			else {
    				train[tidx] = train[tidx] >> 1;	// 앞으로 보낸다. 원래 제일 앞에 있던 좌석은 자동적으로 제거된다.
    			}
    		}
    	}

    	Set<Integer> set = new HashSet<>();
    	for(int i = 1; i < n + 1; i++) {
    		set.add(train[i]);
    	}
    	System.out.println(set.size());
    	br.close();
	}


	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

비트 마스킹을 제대로 써본 문제.
다음에 혼자 해결 할 수 있도록 복습이 필요한 문제이다.

개선할 점