[프로그래머스] level 2 [1차] 프렌즈4블록

문제 설명

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록".
같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.

블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.

만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.

위 초기 배치를 문자로 표시하면 아래와 같다.

TTTANT
RRFACC
RRRFCC
TRRRAA
TTMMMF
TMMTTJ

각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다
입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.

---

문제 풀이 - 파이썬

def solution(m, n, board):
    
    board = [list(row) for row in board]
    ans = 0
    
    # while loop
    while True:
        coords = set()
        for row in range(m - 1): 
            for col in range(n - 1):
                a,b = board[row][col], board[row][col + 1]
                c,d = board[row + 1][col], board[row + 1][col + 1]

                if (a == b) and (b == c) and (c == d) and (a != ""):   
                    coords.add((row, col))
                    coords.add((row, col + 1))
                    coords.add((row + 1, col))
                    coords.add((row + 1, col + 1))
        if not coords:
            break

        ans += len(coords)
        
        # 초기화
        for c in coords:
            row = c[0]
            col = c[1]
            board[row][col] = ""
       
        # rearrange
        for col in range(n):
            stack = []
            for row in range(m):
                if board[row][col] != "":
                    stack.append(board[row][col])
                    
            for row in range(m - 1, -1, -1):
                if stack:
                    board[row][col] = stack.pop()
                else:
                    board[row][col] = ""
                        
    return ans

 

• 풀이 요약
  • 일단 보드를 순회하면서 4개의 블록이 있는지 찾는다
    • 1)있으면, 각 블록의 좌표를 coords 라는 set안에 담는다
      • while loop 밖에 있는 answer에 coords의 갯수 (= 블록의 갯수)를 더해준다 
      • coords 안에 담은 후, coords에 있는 좌표값들의 블록을 빈 공간으로 만들어준다 (나는 무난하게 ""을 사용했는데, 프로그래머스에서 다른 사람의 풀이를 보니까 "팡"같은 귀여운 걸 고르신 분도 계셨다 ㅋㅋ)
      • 그다음 보드를 column으로 순회하면서 빈 공간이 아닌 남은 블록들을 차례대로 stack에 넣어주고, 그리고 밑부터 그 column을 다시 쓰는 방식으로 했다 (덮어씌움)
    • 2) 없으면, 4개블록 세트가 없으므로 while loop에서 break하고, answer을 그래도 리턴해주면 된다
• 내가 생각한 문제의 핵심
  • 4개의 블록을 찾으면, 각 블록의 좌표를 set안에 담을때 set을 활용해서 반복되는 좌표는 자동으로 제거한다
  • 다른건 다 그럭저럭 괜찮았는데, 블록이 "떨어지는" 것을 구현하는 부분에서 가장 막혔다... 이부분은 힌트가 가장 큰 도움이 됐다. 그리고 전체적인 while loop을 어떻게 구현해야할지 처음에는 헷갈렸는데 생각해보니까 그냥 4개블록세트를 찾지 못하면 끝나는 거여서 그냥 while true + break를 사용했다. 

 

문제풀이 - 자바

import java.util.Stack;
import java.util.Set;
import java.util.HashSet;
import java.util.Objects;


class Solution {
    // tuple구현
    // public record Coordinate(int r, int c) {}

    public int solution(int m, int n, String[] board) {
        
        // 보드를 char[][]로 변환
        char[][] char_board = new char[m][n];
        for (int i = 0; i < m; i++) {
            char_board[i] = board[i].toCharArray();
        }

        int answer = 0;
                
        while (true) {
            // tuple을 담을 hashset 구현 
            Set<Coordinate> coords = new HashSet<>();
            for (int row = 0; row < m - 1; row++) {
                for (int col = 0; col < n - 1; col++) {
                    char a = char_board[row][col];
                    char b = char_board[row][col+1];
                    char c = char_board[row+1][col];
                    char d = char_board[row+1][col+1];
                    
                    if (a == b && b == c && c == d && a != ' ') {
                        coords.add(new Coordinate(row, col));
                        coords.add(new Coordinate(row, col+1));
                        coords.add(new Coordinate(row+1, col));
                        coords.add(new Coordinate(row+1, col+1));
                    }
                }
            }
            
            // 4블록 못찾음
            if (coords.size() == 0) {
                break;
            }
            
            // 4블록 찾음
            answer += coords.size();
            
            // 초기화
            for (Coordinate c: coords) {
                int row = c.r;
                int col = c.c;
                char_board[row][col] = ' ';
            }
            
            // 블록 떨어짐 구현
            for (int col = 0; col < n; col++) {
                Stack<Character> s = new Stack<>();
                for (int row = 0; row < m; row++) {
                    char cur = char_board[row][col];
                    if (cur != ' ') {
                        s.push(cur);
                    }
                }
                
                for (int row = m - 1; row >= 0; row--) {
                    if (s.size() > 0) {
                        char_board[row][col] = s.pop();
                    } else {
                        char_board[row][col] = ' ';
                    }
                }
            }
        }
        
        return answer;
    }
}

class Coordinate {
    public int r;
    public int c;
    
    public Coordinate(int r, int c) {
        this.r = r;
        this.c = c;
    }
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Coordinate that = (Coordinate) o;
        return r == that.r && c == that.c; //<<< 이부분 추가
    }

    @Override
    public int hashCode() {
        return Objects.hash(r, c);
    }

}

 

파이썬이 얼마나 심플한지 다시 한번 깨달았다.... 

• 보드를 char[][]로 변환해야했다
• Coordinate 클래스
  • tuple은 자바에 없어서 처음에는 record를 사용했지만 프로그래머스에 에러가 자꾸 떠서 Coordinate 클래스를 따로 만들어줬다ㅠㅠ
  • 오버라이드 메서드 equals, hashCode를 써야했는데, 그 이유는 이 Coordinate 클래스를 HashMap에서 저장을 하는데 내부적으로 set에 추가하기 전에 이미 동일한 객체가 있는지 확인하기 때문이다
    • hashCode - 이 객체의 hashCode를 r,c 기반으로 계산하고 어느 bucket에 들어갈지 결정한다
      • 이렇게 하지 않으면 hashCode는 그냥 객체의 메모리 주소로 계산한다
    • equals - 버켓 안에 이미 객체가 있으면 이게 같은 객체인지 아닌지 판별한다 (duplicate check)
      
      • 같은 객체면 넣지 않는데, r,c 값이 같으면 같은 객체라고 추가해준다
      • 이렇게 하지 않으면, 같은 값의 Coordinate가 있어도 자바는 그냥 메모리로 판별하기 때문에 아예 새로운 객체로 인식하게 된다

생각

• 자바로 풀때마다 더 로우레벨이 돼서 그냥 강제적으로 더 배우게 된다 ㅋㅋ \
• 근데 이 문제 생각보다 재밌어서 나중에 비슷한 문제 유형 더 찾아볼 예정이다.