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

문제

문제 링크

https://www.codetree.ai/missions/2/problems/The-1D-bomb-game?&utm_source=clipboard&utm_medium=text

내 코드

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

public class Main {
    static int endOfArray;
    static int[] arr;
    static int n;
    static int m;

    public static void bomb() {
        int[] tmp = new int[n];
        int tmpIdx = 0;    // 옮겨 담을 배열의 인덱스
        int arrIdx = 0;    // 현재 배열의 인덱스
        while (arrIdx < endOfArray) {
            int std = arr[arrIdx];
            int stdIdx = arrIdx;
            int count = 1;

            while (++arrIdx < endOfArray && arr[arrIdx] == std) count++;

            if (count < m) {
                for (int i = stdIdx; i < arrIdx; i++) {
                    tmp[tmpIdx++] = arr[i];
                }
            }

        }

        arr = tmp;
        endOfArray = tmpIdx;
    }

    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());
        arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        // 연속된 1개면 모든 폭탄이 터짐 -> 굳이 배열 순회할 필요 없음
        if (m == 1) {
            System.out.println(0);
            return;
        }

        endOfArray = n;
        int before = n;
        while (true) {
            bomb();
            // 배열의 개수가 이전과 변화가 없다면 더이상 m개 이상 연속된 폭탄이 없다는 의미
            if (before == endOfArray) break;
            before = endOfArray;
        }

        System.out.println(endOfArray);
        for (int i = 0; i < endOfArray; i++) {
            System.out.println(arr[i]);
        }

    }
}

설명

bomb()

• arr 배열 순회
• 매번 연속된 숫자가 있으면 그만큼 arrIdx를 증가시킨다
  • 증가시킬 때, 연속된 원소의 개수를 세기 위해 count++ 진행
  • 구현하고 나서 보니깐 그냥 arrIdx - stdIdx 가 곧 연속된 원소의 개수였음..ㅋ
• 그리고 나서 count와 m을 비교함
  • 만약 m개 이상 연속된 경우가 아니라면 stdIdx에서부터 arrIdx 전까지 배열의 값들을 tmp로 옮긴다
  • 만약 count < m 이라면 그냥 진행하면 된다
    • 이렇게 하면 자동적으로 연속된 숫자들을 건너뛴거랑 다름 없음
• 외부 while문이 끝나면 arr에 tmp를 넣고 배열의 끝을 원소 개수에 맞게 설정한다

main()의 while문

• 이전 배열의 길이를 before 변수에 넣어두고 bomb() 진행
• 그 후, 이전 배열의 길이(before)와 현재 배열의 길이(endOfArray)를 비교한다
  • 만약 길이가 같다면 m개 이상 연속된 폭탄이 없다는 것 → while 탈출~~