[코드 트리] 1차원 폭발 게임 (JAVA)

[코드 트리] 1차원 폭발 게임 (JAVA)

🗒️알고리즘 분류

#시뮬레이션 #simulation

✏️문제 설명

이 문제에선 1차원 배열로 숫자들(숫자가 쓰여있는 폭탄들💣)이 선언되어 있다.

배열의 숫자들 중 M개 이상 연속으로 같은 숫자가 적혀있는 폭탄들은 연속된 폭탄들 전부 터지게 된다.

폭탄이 터지고 난 후에 중력으로 인해 다시 폭탄들이 아래로 쌓인 후, 다시 숫자들 중에 M개 이상 연속으로 같은 숫자가 적혀있는 폭탄들은 터지게 된다.
위의 과정을 M개 이상 연속으로 같은 숫자가 적혀있는 폭탄들이 없어질 때 까지 반복한다.

📌기억할 만한 포인트

여기서 포인트는 배열이 1차원이라는 점이다.

2차원 배열인 경우는 중력이 작용하는 방향 기준으로 가장 아래인 N-1 부터 0 까지 숫자를 감소 시키면서 아직 안터지고 남은 폭탄이 있는 경우에만 tempArr 배열에 옮겨담고, tempArr 값을 기존 배열에 다시 옮겨준다.

하지만, 1차원 배열에서는 똑같이 N-1 부터 0 까지 숫자를 감소 시키면서 탐색을 할 수 있지만, 앞(0)에서부터 뒤(N-1)까지 탐색하는 것이 좋다.

왜냐하면, 1차원 배열이라는 것 자체가 0 부터 채워지는 것이 자연스럽고, 이것을 구현할 때도 N-1 부터 임의의 점(endOfArray )을 관리하는 것 보다 0 부터 endOfArray 로 관리하는 것이 더 쉽다.

📝풀이 코드(JAVA)

import java.util.*;

public class Main {
    private static final int BLANK = 0;
    private static int N = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        sc.close(); 

        N = n;

        while (true) {
            boolean isExploded = false;

            for (int start = 0; start < N; ++start) {
                if (arr[start] == 0) {
                    continue;
                }
                int end = getEndIndexOfExplosion(arr, start, arr[start]);

                if (end - start + 1 >= m) {
                    bomb(arr, start, end);
                    isExploded = true;
                }
            }

            if (isExploded) {
                gravity(arr);
            } else {
                break;
            }
        }
        
        System.out.println(N);
        for (int i = 0; i < N; ++i) {
            if (arr[i] != BLANK) {
                System.out.println(arr[i]);
            }
        }
        return;
    }

    private static int getEndIndexOfExplosion(int[] arr, int start, int num) {
        int end = start; 
        for (int i = start + 1; i < N; ++i) {
            if (arr[i] == num) {
                end = i;
            } else {
                break;
            }
        }   
        return end;
    }

    private static void bomb(int[] arr, int start, int end) {
        for (int i = start; i <= end; ++i) {
            arr[i] = BLANK;
        }
    }

    private static void gravity(int[] arr) {
        int count = 0;
        int[] tempArr = new int[N];
        int endOfTempArr = 0;

        for (int i = 0; i < N; ++i) {
            if (arr[i] != BLANK) {
                tempArr[endOfTempArr++] = arr[i];
            }
        }

        N = endOfTempArr;

        for (int i = 0; i < N; ++i) {
            arr[i] = tempArr[i];
        }
    }
}

⏰총 풀이시간

• 120분;;