[자바/Simulation] 백준 23796. 2,147,483,648 게임

🤔 INTUITION

그냥 중력 시뮬 문제로 이해했습니다. 다만, 합쳐진 숫자였는지 여부 체크를 곁들인...

 

중력 적용 중 숫자가 동일할 경우 merge 연산이 수행되어야 하는데, 이게 연속적으로 발생할 수 없다는 게 이 문제의 유일한 포인트로 보였습니다. merge 연산 여부를 체크하는 걸 어떻게 할까 하다가, 저는 int 범위 이상의 숫자를 merge 연산 결과에 더해줘서 그 이후로는 이 숫자가 그 어떤 숫자와도 일치하지 않도록 해서 중복 연산되지 않도록 처리해 줬습니다. 이는 다시 배열을 업데이트 할 때 mod 연산으로 제거해 줬습니다.

✅ ALGORITHM

• 시뮬레이션

1. map을 저장합니다.
2. int[] temp 를 이용하여 한 줄 한 줄 중력을 적용해 줍니다. 만약, 숫자가 합쳐지는 경우에는 10^10 제곱을 더해줘서 다시는 합쳐질 수 없게 처리했습니다.
3. 중력 적용이 끝난 뒤에 배열 업데이트 시 10^10 제곱으로 mod 연산을 해줘서 연산 여부를 초기화해줬습니다.

🔎 COMPLEXITY

• 시간복잡도 : O(N^2) -> 124 ms
• 공간복잡도 : O(N^2) -> 14252 KB

public class BOJ_23796_2147483648게임 {
    private static long[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        map = new long[8][8];

        for (int i = 0; i < 8; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 8; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        String cmd = br.readLine();
        go(cmd);

        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                sb.append(map[i][j] + " ");
            }
            sb.append("\n");
        }
        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }

    private static void go(String cmd) {
        long[] temp;
        int tdx;
        if (cmd.equals("R")) { // RIGHT
            for (int i = 0; i < 8; i++) {
                temp = new long[8];
                tdx = 0;
                for (int j = 7; j >= 0; j--) {
                    if (map[i][j] > 0) {
                        // collapse 되는 숫자가 있는 경우
                        if (tdx > 0 && temp[tdx - 1] == map[i][j]) {
                            tdx--;
                            temp[tdx++] += map[i][j] + (long) 1e10;
                            continue;
                        }
                        temp[tdx++] = map[i][j];
                    }
                }
                // 커밋
                for (int j = 0; j < 8; j++) {
                    map[i][7-j] = temp[j] % (long) 1e10;
                }
            }
        } else if (cmd.equals("L")) { // LEFT
            for (int i = 0; i < 8; i++) {
                temp = new long[8];
                tdx = 0;
                for (int j = 0; j < 8; j++) {
                    if (map[i][j] > 0) {
                        if (tdx > 0 && temp[tdx - 1] == map[i][j]) {
                            tdx--;
                            temp[tdx++] += map[i][j] + (long) 1e10;
                            continue;
                        }
                        temp[tdx++] = map[i][j];
                    }
                }
                for (int j = 0; j < 8; j++) {
                    map[i][j] = temp[j] % (long) 1e10;
                }
            }
        } else if (cmd.equals("U")) { // UP
            for (int j = 0; j < 8; j++) {
                temp = new long[8];
                tdx = 0;
                for (int i = 0; i < 8; i++) {
                    if (map[i][j] > 0) {
                        if (tdx > 0 && temp[tdx - 1] == map[i][j]) {
                            tdx--;
                            temp[tdx++] += map[i][j] + (long) 1e10;
                            continue;
                        }
                        temp[tdx++] = map[i][j];
                    }
                }
                for (int i = 0; i < 8; i++) {
                    map[i][j] = temp[i] % (long) 1e10;
                }
            }
        } else if (cmd.equals("D")) {
            for (int j = 0; j < 8; j++) {
                temp = new long[8];
                tdx = 0;
                for (int i = 7; i >= 0; i--) {
                    if (map[i][j] > 0) {
                        if (tdx > 0 && temp[tdx - 1] == map[i][j]) {
                            tdx--;
                            temp[tdx++] += map[i][j] + (long) 1e10;
                            continue;
                        }
                        temp[tdx++] = map[i][j];
                    }
                }
                for (int i = 7; i >= 0; i--) {
                    map[i][j] = temp[7-i] % (long) 1e10;
                }
            }
        }

    }
}