[자바] 백준 15787: 기차가 어둠을 헤치고 은하수를, 2가지 풀이(비트마스킹, 문자열)
본 글에서는 비트 마스킹과 문자열로 푸는 방법을 설명한다. 난 처음에 문자열을 사용하여 어렵지 않게 코드를 작성하였는데, 구글링을 해보니 비트 마스킹을 사용하여 대부분이 해결하고 있었다. 비트 마스킹을 처음 접한다면 이해가 어려울 수 있겠지만, 어렵다고 포기하지 말고 다른 글도 참고하면서 이해해 보도록 하자. (나도 비트 마스킹은 처음 알았고, 손으로 그려가며 이해했다.)
방법 1: StringBuilder를 사용한다.
나는 문자열을 사용하여 코드를 작성했는데, String이 아닌 StringBuilder를 사용했다. 자바에서는 String 클래스의 경우 불변 객체이고, StringBuilder는 가변 객체이다. 따라서 String 객체를 사용하여 추가, 삭제, 수정 연산을 수행하면 새로운 객체를 생성하여 복사 작업이 발생한다. 새로운 배열에 기존 값을 복시해야 하므로 O(N) 시간 복잡도가 발생한다.
그러나 StringBuilder는 가변 객체이므로 추가, 삭제, 수정 작업에서 O(1)로 해결할 수 있는 다양한 메서드를 제공한다.
1번 명령어는 특정 자리(seatIdx)에 앉는 것이므로, setCharAt() 메서드를 사용하여 코드를 작성한다.
if (order == 1) {
int seatIdx = Integer.parseInt(inputs[2]) - 1;
selectTrain.setCharAt(seatIdx, '1');
}
2번 명령어는 특정 자리를 비우는 것이다. 1번과 똑같이 setCharAt()을 사용하되, 0을 저장하여 자리를 비워준다.
else if (order == 2) {
int seatIdx = Integer.parseInt(inputs[2]) - 1;
selectTrain.setCharAt(seatIdx, '0');
}
3번 명령어는 자리를 한 칸씩 뒤로 이동하는 것이다. 한 칸 뒤로 이동했을 때, 가장 앞에는 아무도 탑승하지 않게 된다.
(1) 0번 인덱스에 새로운 자리를 만들어주고, (2) 21번째 자리는 제거한다. 기차는 최대 20 좌석이 존재한다. 그러나 (1)번을 수행하면서 21개가 되었으므로, 가장 마지막에 존재하는 좌석을 제거하여 20개로 맞춰준다.
else if (order == 3) {
selectTrain.insert(0, '0');
selectTrain.deleteCharAt(20);
}
4번 명령어는 자리를 한 칸씩 앞으로 이동하는 것이다. 한 칸 앞으로 이동했을 때, 가장 뒤에는 아무도 탑승하지 않게 된다.
(1) 가장 마지막에 새로운 자리를 만들어 주고, (2) 0번째 자리는 제거한다. (2)번 과정을 수행하는 이유는 3번 명령어처럼 최대 20개의 좌석으로 맞추기 위해서이다.
else {
selectTrain.append("0");
selectTrain.deleteCharAt(0);
}
최종 코드는 다음과 같이 된다.
public class Main {
static int N, M;
static List<StringBuilder> list = new ArrayList<>();
// 기차에는 20개의 좌석이 존재한다.
static final StringBuilder init = new StringBuilder("00000000000000000000");
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = br.readLine().split(" ");
N = Integer.parseInt(inputs[0]);
M = Integer.parseInt(inputs[1]);
// N개의 기차를 저장한다.
// 각 기차에는 20개의 좌석이 존재한다.
for (int i = 0; i < N; i++) {
list.add(new StringBuilder(init));
}
for (int i = 0; i < M; i++) {
inputs = br.readLine().split(" ");
int order = Integer.parseInt(inputs[0]);
int trainIdx = Integer.parseInt(inputs[1]) - 1;
StringBuilder selectTrain = list.get(trainIdx);
if (order == 1) {
int seatIdx = Integer.parseInt(inputs[2]) - 1;
selectTrain.setCharAt(seatIdx, '1');
} else if (order == 2) {
int seatIdx = Integer.parseInt(inputs[2]) - 1;
selectTrain.setCharAt(seatIdx, '0');
} else if (order == 3) {
selectTrain.insert(0, '0');
selectTrain.deleteCharAt(20);
} else {
selectTrain.append("0");
selectTrain.deleteCharAt(0);
}
}
// Set은 중복 데이터를 저장하지 않는다.
Set<String> set = new HashSet<>();
for (int i = 0; i < N; i++) {
set.add(list.get(i).toString());
}
System.out.println(set.size());
}
}
방법2: 비트 마스킹을 사용한다.
본 글이 비트 마스킹 설명이 목적이 아니므로, 구글링을 통해 기본적인 비트 마스킹 연산에 대해서 찾아보자. 비트 마스킹은 정수를 2진수로 다루어 해결하는 방법이다. 쉬프트 연산(<<, >>), AND(&), OR(|), NOT(~) 등 2진수를 다룰 수 있는 다양한 메서드를 제공한다.
1번 명령어
if (order == 1) {
int seatIdx = Integer.parseInt(inputs[2]) - 1;
trains[trainIdx] |= (1 << seatIdx);
}
2번 명령어
else if (order == 2) {
int seatIdx = Integer.parseInt(inputs[2]) - 1;
trains[trainIdx] &= ~(1 << seatIdx);
}
3번 명령어
else if (order == 3) {
trains[trainIdx] <<= 1;
trains[trainIdx] &= (1 << 20);
}
4번 명령어
else {
trains[trainIdx] >>= 1;
trains[trainIdx] &= ~(1 << 20);
}
비트 마스킹을 사용한 코드는 다음과 같다.
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = br.readLine().split(" ");
int N = Integer.parseInt(inputs[0]);
int M = Integer.parseInt(inputs[1]);
int[] trains = new int[N];
while (M-- > 0) {
inputs = br.readLine().split(" ");
int order = Integer.parseInt(inputs[0]);
int trainIdx = Integer.parseInt(inputs[1]) - 1;
if (order == 1) {
int seatIdx = Integer.parseInt(inputs[2]) - 1;
trains[trainIdx] |= (1 << seatIdx);
} else if (order == 2) {
int seatIdx = Integer.parseInt(inputs[2]) - 1;
trains[trainIdx] &= ~(1 << seatIdx);
} else if (order == 3) {
trains[trainIdx] <<= 1;
trains[trainIdx] &= ~(1 << 20);
} else {
trains[trainIdx] >>= 1;
trains[trainIdx] &= ~(1 << 20);
}
}
Set<Integer> set = new HashSet<>();
for (int train : trains) {
set.add(train);
}
System.out.println(set.size());
}
}