[백준/JAVA] 15787번: 기차가 어둠을 헤치고 은하수를

📖 문제

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

 

 

 

💡  풀이 방식

• 구현 & 비트마스킹

 (비트마스킹 안 쓰고 풀었다.)

 

사용 자료구조

- 2차원 int형 배열 [기차 수 N][기차 좌석 수 20]

- 열차 상태를 String형으로 받아 저장할 Set (중복 제거)

 

1. 입력받은 숫자에 따라 명령을 수행한다.

- 숫자가 1이면, 해당 칸을 1로 만들어 사람을 태운다.

- 숫자가 2면, 해당 칸을 0으로 만들어 사람을 하차시킨다.

- 숫자가 3이면, 모두 한 칸씩 뒤로 이동시키고 맨 뒷사람은 하차시킨다.

for(int i = 20 ; i > 1 ; i--) {
    arr[tIdx][i] = arr[tIdx][i - 1];
}

arr[tIdx][1] = 0;

 

- 숫자가 4면, 모두 한 칸씩 앞으로 이동시키고 맨 앞 사람은 하차시킨다.

for(int i = 1 ; i < 20 ; i++) {
    arr[tIdx][i] = arr[tIdx][i + 1];
}

arr[tIdx][20] = 0;

 

 

2. 기차 열차 수를 저장한 배열을 Set형에 String형으로 받고 저장한다.

3. 해당 HashSet의 사이즈를 구한다. (중복 제거)

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static int[][] trains;
    static Set<String> set = 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());   // 명령 수
 
        trains = new int[N + 1][21];
 
        while(M --> 0) {
            String[] str = br.readLine().split(" ");
 
            int cmd = Integer.parseInt(str[0]);
            int train = Integer.parseInt(str[1]);
 
            if(str.length == 2) {
                move(cmd, train);
            }
            else {
                int seat = Integer.parseInt(str[2]);
                solve(cmd, train, seat);
            }
        }
 
        // 열차 상태를 문자열로 만들어 Set에 저장
        for(int i = 1 ; i <= N ; i++) {
            StringBuilder sb = new StringBuilder();
            for(int j = 1 ; j <= 20 ; j++) {
                sb.append(trains[i][j] + " ");
            }
            set.add(sb.toString());
        }
 
        // set 크기 구하기 (set은 자동 중복 제거)
        System.out.println(set.size());
    }
 
    private static void solve(int cmd, int tIdx, int seat) {
        if(cmd == 1) {
            trains[tIdx][seat] = 1;
        }
        else if(cmd == 2) {
            trains[tIdx][seat] = 0;
        }
 
        return;
    }
 
    private static void move(int cmd, int tIdx) {
        if(cmd == 3) {  // 모두 한 칸씩 뒤로 이동
            for(int i = 20 ; i > 1 ; i--) {
                trains[tIdx][i] = trains[tIdx][i - 1];
            }
            trains[tIdx][1] = 0;
        }
        else if(cmd == 4) { // 모두 한 칸씩 앞으로 이동
            for(int i = 1 ; i < 20 ; i++) {
                trains[tIdx][i] = trains[tIdx][i + 1];
            }
            trains[tIdx][20] = 0;
        }
 
        return;
    }
}
 

 

 

 

➕ 다른 풀이 방식

- 비트마스킹을 활용한 풀이!

// 1. 원소 추가 (x번 비트를 1로 바꿈)
trains[i] |= (1 << x)

// 2. 원소 삭제 (x번 비트만 1, 나머지 비트는 0으로 바꿈)
trains[i] &= ~(1 << x)

// 3. 기차 한 칸씩 뒤로 밀고, 맨 뒤 사람 하차시키기
trains[i] = (trains[i] & ~(1 << 19)) << 1;

// 4. 기차 맨 앞 사람 하차시키고, 한 칸씩 앞으로 당기기
trains[i] = (trains[i] & ~(1 << 0)) >> 1;

 

[알고리즘] Java / 백준 / 기차가 어둠을 헤치고 은하수를 / 15787

백준 15787번 : 기차가 어둠을 헤치고 은하수를(Java)

---

💦 어려웠던 점

- 뒤로 이동시킬 때 역방향으로 채웠어야 했는데 정방향으로 해서 틀렸었다,,,ㅠ

- 비트마스킹..에 익숙하지 않아 비트마스킹 풀이를 이해하는 것이 쉽지 않았다.ㅠ

 

🧐 새로 알게 된 내용

- 비트마스킹 : 원소 추가, 삭제, 토글, 합집합, 교집합 등 다양한 연산 빠르게 구현 가능

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이 참고

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

 

 

✔ 비트마스킹

: 원소 추가, 삭제, 토글, 합집합, 교집합 등 다양한 연산 빠르게 구현 가능

[알고리즘] 비트마스킹(bitmasking) 이란