프렌즈 4블록

2026.06.28

문제 풀이

1차 실행 오류

---

63.6/100

블록을 내릴 때 구조가 잘못되었음

O O O O O
O O O O O
O O O O O
X X O O O
X X O O O
O O O O O
X X O O O
X X O O O
O O O O O

와 같은 상황에서 empty == 4일 때,
[5][0] = [1][0]
[1][0] = ' '이 되는 문제가 발생하게 됨

---

import java.util.List;
import java.util.ArrayList;

class Solution {
    public int solution(int m, int n, String[] board) {
        int answer = 0;
        List<int[]> remove = new ArrayList<>(); // 제거 할 블록의 인덱스 저장
        boolean isFin = false; // 제거할 블록의 유/무 표시
        
        char blocks[][] = new char[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                blocks[i] = board[i].toCharArray();
            }
        }
        
        while(true) {
            if (isFin) {
                break;
            }
            for (int i = 0; i < m - 1; i++) {
                for (int j = 0; j < n - 1; j++) {
                    char b1 = blocks[i][j];
                    char b2 = blocks[i][j + 1];
                    char b3 = blocks[i + 1][j];
                    char b4 = blocks[i + 1][j + 1];
                    
                    if (b1 == b2 && b2 == b3 && b3 == b4 && b1 != ' ') { // 2 x 2 블록이 모두 같을 때
                        remove.add(new int[]{i, j});
                        remove.add(new int[]{i, j + 1});
                        remove.add(new int[]{i + 1, j});
                        remove.add(new int[]{i + 1, j + 1});
                        // 해당하는 인덱스 모두 저장
                    }
                }
            }
            if (remove.isEmpty()) { // 더 이상 제거할 블록이 없을 때
                isFin = true;
            }
            for (int i = 0; i < remove.size(); i++) { // 블록에서 전체 제거
                if (blocks[remove.get(i)[0]][remove.get(i)[1]] == ' ') {
                    continue;
                }
                else {
                    blocks[remove.get(i)[0]][remove.get(i)[1]] = ' ';
                    answer++;
                }
            }
            remove.clear(); // remove 원소 전체 제거
            
            // 블록 내리기
            for (int i = 0; i < n; i++) {
                int empty = 0;
                for (int j = m - 1; j >= 0; j--) {
                    if (empty > 0 && blocks[j][i] != ' ') { 
                        blocks[j + empty][i] = blocks[j][i];
                        blocks[j][i] = ' ';
                    }
                    if (blocks[j][i] == ' ') { // 비어있는 공간 발견 시,
                        empty++;
                    }
                }
            }
        }
        return answer;
    }
}

2차 실행 오류

---

81.8/100

Deque를 사용해서 블록을 내리는 구조를 바꾸었음

if (q.size() > 0 && blocks[j][i] != ' ') {
	int p[] = q.poll();
    blocks[p[0]][p[1]] = blocks[j][i];
    blocks[j][i] = ' ';
}
if (blocks[j][i] == ' ') { // 비어있는 공간 발견 시,
	q.offer(new int[]{j, i});
}

에서 이미 아래의 조건문에 q.offer(new int[]{j, i})가 있으므로 중복됨

---

import java.util.List;
import java.util.ArrayList;
import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int solution(int m, int n, String[] board) {
        int answer = 0;
        List<int[]> remove = new ArrayList<>(); // 제거 할 블록의 인덱스 저장
        boolean isFin = false; // 제거할 블록의 유/무 표시
        
        char blocks[][] = new char[m][n];
        for (int i = 0; i < m; i++) { // char 배열로 저장
            for (int j = 0; j < n; j++) {
                blocks[i] = board[i].toCharArray();
            }
        }
        
        while(true) {
            if (isFin) {
                break;
            }
            for (int i = 0; i < m - 1; i++) {
                for (int j = 0; j < n - 1; j++) {
                    char b1 = blocks[i][j];
                    char b2 = blocks[i][j + 1];
                    char b3 = blocks[i + 1][j];
                    char b4 = blocks[i + 1][j + 1];
                    
                    if (b1 == b2 && b2 == b3 && b3 == b4 && b1 != ' ') { // 2 x 2 블록이 모두 같을 때
                        remove.add(new int[]{i, j});
                        remove.add(new int[]{i, j + 1});
                        remove.add(new int[]{i + 1, j});
                        remove.add(new int[]{i + 1, j + 1});
                        // 해당하는 인덱스 모두 저장
                    }
                }
            }
            if (remove.isEmpty()) { // 더 이상 제거할 블록이 없을 때
                isFin = true;
            }
            for (int i = 0; i < remove.size(); i++) { // 블록에서 전체 제거
                if (blocks[remove.get(i)[0]][remove.get(i)[1]] == ' ') {
                    continue;
                }
                else {
                    blocks[remove.get(i)[0]][remove.get(i)[1]] = ' ';
                    answer++;
                }
            }
            remove.clear(); // remove 원소 전체 제거
            
            // 블록 내리기
            Deque<int[]> q = new ArrayDeque<>();
            for (int i = 0; i < n; i++) {
                q.clear();
                for (int j = m - 1; j >= 0; j--) {
                    if (q.size() > 0 && blocks[j][i] != ' ') {
                        int p[] = q.poll();
                        blocks[p[0]][p[1]] = blocks[j][i];
                        q.offer(new int[]{j, i});
                        blocks[j][i] = ' ';
                    }
                    if (blocks[j][i] == ' ') { // 비어있는 공간 발견 시,
                        q.offer(new int[]{j, i});
                    }
                }
            }
        }
        return answer;
    }
}

나의 코드

소요 시간: 1시간 18분

시간 복잡도: $O((m * n)²)$

import java.util.List;
import java.util.ArrayList;
import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int solution(int m, int n, String[] board) {
        int answer = 0;
        List<int[]> remove = new ArrayList<>(); // 제거 할 블록의 인덱스 저장
        boolean isFin = false; // 제거할 블록의 유/무 표시
        
        char blocks[][] = new char[m][n];
        for (int i = 0; i < m; i++) { // char 배열로 저장
            for (int j = 0; j < n; j++) {
                blocks[i] = board[i].toCharArray();
            }
        }
        
        while(true) {
            if (isFin) {
                break;
            }
            for (int i = 0; i < m - 1; i++) {
                for (int j = 0; j < n - 1; j++) {
                    char b1 = blocks[i][j];
                    char b2 = blocks[i][j + 1];
                    char b3 = blocks[i + 1][j];
                    char b4 = blocks[i + 1][j + 1];
                    
                    if (b1 == b2 && b2 == b3 && b3 == b4 && b1 != ' ') { // 2 x 2 블록이 모두 같을 때
                        remove.add(new int[]{i, j});
                        remove.add(new int[]{i, j + 1});
                        remove.add(new int[]{i + 1, j});
                        remove.add(new int[]{i + 1, j + 1});
                        // 해당하는 인덱스 모두 저장
                    }
                }
            }
            if (remove.isEmpty()) { // 더 이상 제거할 블록이 없을 때
                isFin = true;
            }
            for (int i = 0; i < remove.size(); i++) { // 블록에서 전체 제거
                if (blocks[remove.get(i)[0]][remove.get(i)[1]] == ' ') {
                    continue;
                }
                else {
                    blocks[remove.get(i)[0]][remove.get(i)[1]] = ' ';
                    answer++;
                }
            }
            remove.clear(); // remove 원소 전체 제거
            
            // 블록 내리기
            Deque<int[]> q = new ArrayDeque<>();
            for (int i = 0; i < n; i++) {
                q.clear();
                for (int j = m - 1; j >= 0; j--) {
                    if (q.size() > 0 && blocks[j][i] != ' ') {
                        int p[] = q.poll();
                        blocks[p[0]][p[1]] = blocks[j][i];
                        blocks[j][i] = ' ';
                    }
                    if (blocks[j][i] == ' ') { // 비어있는 공간 발견 시,
                        q.offer(new int[]{j, i});
                    }
                }
            }
        }
        return answer;
    }
}

AI 코드

시간 복잡도: $O((m * n)²)$

---

List를 사용하는 대신 boolean을 사용하여
시간 복잡도는 동일하지만, List의 오버헤드를 제거함

---

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int solution(int m, int n, String[] board) {
        int answer = 0;
        char[][] blocks = new char[m][n];
        for (int i = 0; i < m; i++) {
            blocks[i] = board[i].toCharArray();
        }

        while (true) {
            boolean[][] removed = new boolean[m][n];
            boolean found = false;

            for (int i = 0; i < m - 1; i++) {
                for (int j = 0; j < n - 1; j++) {
                    char b = blocks[i][j];
                    if (b != ' ' && b == blocks[i][j+1] && b == blocks[i+1][j] && b == blocks[i+1][j+1]) {
                        removed[i][j] = removed[i][j+1] = true;
                        removed[i+1][j] = removed[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 (removed[i][j]) {
                        blocks[i][j] = ' ';
                        answer++;
                    }
                }
            }

            Deque<int[]> q = new ArrayDeque<>();
            for (int i = 0; i < n; i++) {
                q.clear();
                for (int j = m - 1; j >= 0; j--) {
                    if (q.size() > 0 && blocks[j][i] != ' ') {
                        int[] p = q.poll();
                        blocks[p[0]][p[1]] = blocks[j][i];
                        blocks[j][i] = ' ';
                    }
                    if (blocks[j][i] == ' ') q.offer(new int[]{j, i});
                }
            }
        }

        return answer;
    }
}