[JAVA 문제 풀이] 350. 프렌즈4블록

내가 작성한 코드

class Solution {
    public int solution(int m, int n, String[] board) {
        char[][] map = new char[m][n];
        
        // 문자열 배열을 문자 2차원 배열화
        for (int i = 0; i < m; i++) {
            map[i] = board[i].toCharArray();
        }

        int answer = 0;

        while (true) {
            boolean[][] marked = new boolean[m][n]; // 제거된 블록 표시할 2차원 배열
            boolean found = false;

            // 2x2 블록 찾아서 해당 위치의 marked배열에 표시
            for (int i = 0; i < m - 1; i++) {
                for (int j = 0; j < n - 1; j++) {
                    char c = map[i][j];
                    if (c == ' ') continue;
                    if (c == map[i][j + 1] &&
                        c == map[i + 1][j] &&
                        c == map[i + 1][j + 1]) {
                        marked[i][j] = true;
                        marked[i][j + 1] = true;
                        marked[i + 1][j] = true;
                        marked[i + 1][j + 1] = true;
                        found = true;
                    }
                }
            }

            if (!found) break; // 더 이상 지울 블록이 없으면 종료

            // 제거된 블록 수 카운트 및 제거
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (marked[i][j]) {
                        map[i][j] = ' ';
                        answer++;
                    }
                }
            }

            // 블록 아래로 내리기 (열 단위 처리)
            for (int j = 0; j < n; j++) {
                int emptyRow = m - 1; // 가장 아래 행

                for (int i = m - 1; i >= 0; i--) {
                    if (map[i][j] != ' ') { // 현재 위치가 비어있지 않으면
                        char temp = map[i][j]; // 현재 위치의 문자를 저장
                        map[i][j] = ' '; // 현재 위치를 비어있는 문자로 바꾸기
                        map[emptyRow][j] = temp; // 가장 아래 행의 문자를 현재 위치로 바꾸기
                        emptyRow--; // 위의 행으로 이동
                    }
                }
            }
        }

        return answer;
    }
}

다른 사람의 코드

import java.util.*;
import java.util.stream.*;

class Solution {
    public int solution(int m, int n, String[] board) {
        return new Board(board).play();
    }

    // 보드 상태를 관리하고 로직을 수행하는 내부 클래스
    private static class Board {
        private final List<List<Block>> board;

        // 생성자1 >> 블록 리스트를 직접 전달받아 초기화
        public Board(List<List<Block>> board) {
            this.board = board;
        }

        // 생성자2 >> String[] board를 받아 Block 객체들로 변환하여 초기화
        public Board(String[] board) {
            this(
                    IntStream.range(0, board.length) // 행 인덱스 반복
                            .mapToObj(i -> IntStream.range(0, board[i].length()) // 열 인덱스 반복
                                    .mapToObj(j -> new Block(i + String.valueOf(j), String.valueOf(board[i].charAt(j))))
                                    .collect(Collectors.toList())) // 한 줄을 Block 리스트로 변환
                            .collect(Collectors.toList()) // 전체 board를 List<List<Block>>으로 변환
            );
        }

        // 게임 실행 함수 >> 블록을 제거하고 아래로 내리는 과정을 반복
        public Integer play() {
            int popCount = 0;
            Set<Block> removableBlocks;

            // 더 이상 지울 블록이 없을 때까지 반복
            while ((removableBlocks = getRemovableBlocks()).size() > 1) {
                popCount += removableBlocks.size(); // 지운 블록 수 누적
                removableBlocks.forEach(Block::toBlank); // 블록을 빈 문자열로 변경
                pushDown(); // 위의 블록들을 아래로 내림
            }

            return popCount;
        }

        // 2x2 같은 블록들을 찾아 removableBlocks로 반환
        private Set<Block> getRemovableBlocks() {
            Set<Block> removableBlocks = new HashSet<>();

            for (int i = 0, height = board.size() - 1; i < height; i++) {
                for (int j = 0, width = board.get(0).size() - 1; j < width; j++) {
                    Block block = board.get(i).get(j);
                    addRemovableBlocks(removableBlocks, i, j, block); // 해당 블록 기준으로 검사
                }
            }

            return removableBlocks;
        }

        // 현재 위치에서 2x2가 동일한 블록이면 removableBlocks에 추가
        private void addRemovableBlocks(Set<Block> removableBlocks, int i, int j, Block block) {
            if (block.isBlank())
                return; // 빈 블록이면 검사할 필요 없음

            Set<Block> blocks = new HashSet<>();
            blocks.add(block);

            // 2x2 영역 검사
            for (int k = i; k <= i + 1; k++) {
                for (int l = j; l <= j + 1; l++) {
                    if (k == i && l == j)
                        continue; // 현재 기준 블록은 생략

                    if (isInvalidPosition(k, l))
                        return; // 범위를 벗어나면 중단

                    Block currentBlock = board.get(k).get(l);
                    if (block.hasSameNameWith(currentBlock)) {
                        blocks.add(currentBlock);
                    }
                }
            }

            // 4개 다 일치하면 removableBlocks에 추가
            if (blocks.size() > 3) {
                removableBlocks.addAll(blocks);
                removableBlocks.forEach(Block::check); // 디버깅용 플래그
            }
        }

        // 전체 열에 대해 블록을 아래로 내림
        private void pushDown() {
            for (int j = 0, width = board.get(0).size(); j < width; j++) {
                pushDown(j);
            }
        }

        // 특정 열(j)에 대해 위 블록을 아래 빈칸으로 내림
        private void pushDown(int j) {
            int firstBlankIndex = getFirstBlankIndex(j); // 아래에서부터 빈칸 찾기
            int firstNotBlankIndexAfterBlank = getFirstNotBlankIndexAfterBlank(j, firstBlankIndex); // 그 위에 블록 찾기

            while (firstBlankIndex >= 0 && firstNotBlankIndexAfterBlank >= 0) {
                Block blank = board.get(firstBlankIndex).get(j);
                Block notBlank = board.get(firstNotBlankIndexAfterBlank).get(j);

                // 아래 빈칸에 블록을 넣고, 원래 자리는 빈칸으로
                board.get(firstBlankIndex).set(j, notBlank);
                board.get(firstNotBlankIndexAfterBlank).set(j, blank);

                // 다음 블록 찾기
                firstBlankIndex = getFirstBlankIndex(j);
                firstNotBlankIndexAfterBlank = getFirstNotBlankIndexAfterBlank(j, firstBlankIndex);
            }
        }

        // 범위 벗어났는지 검사
        private boolean isInvalidPosition(int i, int j) {
            return i >= board.size() || j >= board.get(0).size();
        }

        // 아래에서부터 빈칸인 블록의 행 인덱스를 찾음
        private int getFirstBlankIndex(int j) {
            for (int i = board.size() - 1; i >= 0; i--) {
                if (board.get(i).get(j).isBlank()) {
                    return i;
                }
            }
            return -1;
        }

        // 빈칸 위쪽에 있는 블록의 행 인덱스를 찾음
        private int getFirstNotBlankIndexAfterBlank(int j, int firstBlankIndex) {
            if (firstBlankIndex < 0)
                return -1;

            for (int i = firstBlankIndex - 1; i >= 0; i--) {
                if (!board.get(i).get(j).isBlank()) {
                    return i;
                }
            }

            return -1;
        }
    }

    // 각 블록을 객체로 표현하는 클래스
    private static class Block {
        private static final String BLANK = ""; // 빈 블록을 나타내는 값
        private final String id; // 고유 식별자 (row + col)
        private String name; // 블록 문자
        private boolean checked = false; // 제거 체크 여부 (디버깅용)

        public Block(String id, String name) {
            this.id = id;
            this.name = name;
        }

        public void toBlank() {
            this.name = BLANK; // 블록 제거 처리
        }

        public boolean isBlank() {
            return BLANK.equals(this.name);
        }

        public boolean isChecked() {
            return this.checked;
        }

        public void check() {
            this.checked = true;
        }

        public boolean hasSameNameWith(Block block) {
            return this.name.equals(block.name); // 블록 이름 비교
        }

        // Block 객체 비교 시 id를 기준으로 판단
        @Override
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            Block block = (Block) o;
            return Objects.equals(id, block.id);
        }

        @Override
        public int hashCode() {
            return Objects.hash(id);
        }
    }
}