[백준] 15787번 : 기차가 어둠을 헤치고 은하수를 - 자바[Java]

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

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

 

풀이

기차의 상태를 저장하는 2차원 배열을 선언한 후, 입력하는 명령에 따라 기차의 상태를 변경하면 된다.

그 후 모든 기차를 탐색하여 기차의 상태가 중복되는게 있는지 검사한다.

 

로직

1. n과 m을 입력받는다.

2. 기차의 상태를 저장하는 boolean형 2차원 배열 train을 선언하고, n X 20 크기로 할당한다. 승객이 앉아있으면 해당 위치에 true, 승객이 없으면 false를 저장한다.

3. 명령어를 입력받고, 각 명령에 따라 기차의 상태를 변경한다.

4. 기차의 상태를 문자열에 저장하기 위한 ArrayList<String> list를 선언한다. 또한 은하수를 건널 수 있는 기차의 수를 저장하는 cnt도 선언하고 0으로 초기화한다.

5. 모든 기차의 상태를 탐색한다. 기차의 상태를 문자열로 표현할 때, 승객이 앉아있으면 1, 승객이 없으면 0으로 표현한다. 현재 기차의 상태가 이전 기차의 상태와 중복되지 않았다면, list에 문자열을 저장하고 cnt에 1을 더한다.

6. cnt를 출력한다.

 

코드

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

public class Main {

    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());

        boolean[][] train = new boolean[n][20]; //기차의 상태 저장, 승객이 앉아있으면 true, 없으면 false

        //명령 수행
        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());

            int command = Integer.parseInt(st.nextToken());
            int i, x;

            switch(command) {
                case 1:
                    i = Integer.parseInt(st.nextToken());
                    x = Integer.parseInt(st.nextToken());
                    train[i-1][x-1] = true;
                    break;
                case 2:
                    i = Integer.parseInt(st.nextToken());
                    x = Integer.parseInt(st.nextToken());
                    train[i-1][x-1] = false;
                    break;
                case 3:
                    i = Integer.parseInt(st.nextToken());
                    for (int idx = 19; idx > 0; idx--) {
                        train[i-1][idx] = train[i-1][idx-1];
                    }
                    train[i-1][0] = false;
                    break;
                case 4:
                    i = Integer.parseInt(st.nextToken());
                    for (int idx = 0; idx < 19; idx++) {
                        train[i-1][idx] = train[i-1][idx+1];
                    }
                    train[i-1][19] = false;
                    break;
            }
        }

        ArrayList<String> list = new ArrayList<>(); //기차의 상태를 문자열로 저장
        int cnt = 0; //은하수를 건널 수 있는 기차의 수

        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < 20; j++) {
                if (train[i][j]) sb.append("1"); //승객이 앉아있으면 1
                else sb.append("0"); //승객이 없으면 0
            }

            String str = sb.toString(); //기차의 상태를 문자열로 표현

            //현재 기차의 상태가 이전 기차의 상태와 같지 않으면 list에 저장하고 cnt에 1을 더한다
            if (!list.contains(str)) {
                list.add(str);
                cnt++;
            }
        }

        System.out.println(cnt);
    }
}

 

---

다른 풀이 2

위의 로직에서 모든 기차를 탐색하여 기차의 상태가 중복되는게 있는지 검사하는 로직을 변경했다.

• 기차의 상태를 문자열에 저장하기 위해 ArrayList가 아닌 Set를 선언한다.
• Set은 중복되는 원소는 자동으로 저장하지 않으므로 contains() 메서드를 사용할 필요가 없으며, cnt로 직접 기차의 개수를 세지 않아도 set.size()로 set의 크기를 출력하면 된다.

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

public class Main {

    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());

        boolean[][] train = new boolean[n][20]; //기차의 상태 저장, 승객이 앉아있으면 true, 없으면 false

        //명령 수행
        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());

            int command = Integer.parseInt(st.nextToken());
            int i, x;

            switch(command) {
                case 1:
                    i = Integer.parseInt(st.nextToken());
                    x = Integer.parseInt(st.nextToken());
                    train[i-1][x-1] = true;
                    break;
                case 2:
                    i = Integer.parseInt(st.nextToken());
                    x = Integer.parseInt(st.nextToken());
                    train[i-1][x-1] = false;
                    break;
                case 3:
                    i = Integer.parseInt(st.nextToken());
                    for (int idx = 19; idx > 0; idx--) {
                        train[i-1][idx] = train[i-1][idx-1];
                    }
                    train[i-1][0] = false;
                    break;
                case 4:
                    i = Integer.parseInt(st.nextToken());
                    for (int idx = 0; idx < 19; idx++) {
                        train[i-1][idx] = train[i-1][idx+1];
                    }
                    train[i-1][19] = false;
                    break;
            }
        }

        Set<String> set = new HashSet<>(); // 기차의 상태를 문자열로 저장하는 집합

        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < 20; j++) {
                if (train[i][j]) sb.append("1"); //승객이 앉아있으면 1
                else sb.append("0"); //승객이 없으면 0
            }

            String str = sb.toString(); //기차의 상태를 문자열로 표현
            set.add(str);
        }

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