1. 문제
programmers.co.kr/learn/courses/30/lessons/17679
문제 설명
블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은프렌즈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)을 의미한다
입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.
제한 사항
입력 형식
- 입력으로 판의 높이
m
, 폭n
과 판의 배치 정보board
가 들어온다. - 2 ≦
n
,m
≦ 30 board
는 길이n
인 문자열m
개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.
출력 형식
입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.
입출력 예
m | n | board | answer |
4 | 5 | ["CCBDE","AAADE","AAABF","CCBBF"] | 14 |
6 | 6 | ["TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"] | 15 |
2. 어떻게 풀까?
- 입력으로 주어진
String
배열board
를 이차원 배열로 만든다. - 이차원 배열의 현재 index의 block을 기준으로 block을 지울 수 있는지 확인한다.
- 지운 이후 위쪽의 block들을 아래로 내린다.
- 지울 수 있는 block이 없을 때까지 반복한다.
- 해결 과정은 명확하게 이해할 수 있는데, 이것을 코드로 작성하는데 계속 막히고, 틀렸다. 특히, 지울 수 있는지 확인하는 과정에서
boolean
타입을 선언해서 확인하려했는데, 잘 안됐다. 그래서 답을 참고했다.
3. 코드
테스트 코드
import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.*;
import org.junit.Test;
public class SolutionTest {
@Test
public void test1() {
String[] board = {"CCBDE", "AAADE", "AAABF", "CCBBF"};
assertThat(new Solution().solution(4, 5, board), is(14));
}
@Test
public void test2() {
String[] board = {"TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"};
assertThat(new Solution().solution(6, 6, board), is(15));
}
}
실제 코드
public class Solution {
public int solution(int m, int n, String[] board) {
String[][] table = buildTable(m, n, board);
int count = 0;
while (true) {
int dropBlockCount = countFourBlock(m, n, table);
if (dropBlockCount == 0) {
break;
}
count += dropBlockCount;
dropTable(m, n, table);
}
return count;
}
private String[][] buildTable(int m, int n, String[] board) {
String[][] table = new String[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
table[i][j] = board[i].charAt(j) + "";
}
}
return table;
}
private int countFourBlock(int m, int n, String[][] table) {
boolean[][] check = new boolean[m][n];
for (int row = 0; row < m - 1; row++) {
for (int col = 0; col < n - 1; col++) {
if (table[row][col].equals(".")) {
continue;
}
checkFourBlock(table, check, row, col);
}
}
int count = 0;
for (int row = 0; row < m; row++) {
for (int col = 0; col < n; col++) {
if (check[row][col]) {
count++;
table[row][col] = ".";
}
}
}
return count;
}
private void checkFourBlock(String[][] table, boolean[][] check, int currentRow,
int currentCol) {
String currentBlock = table[currentRow][currentCol];
for (int row = currentRow; row < currentRow + 2; row++) {
for (int col = currentCol; col < currentCol + 2; col++) {
if (!table[row][col].equals(currentBlock)) {
return;
}
}
}
for (int row = currentRow; row < currentRow + 2; row++) {
for (int col = currentCol; col < currentCol + 2; col++) {
check[row][col] = true;
}
}
}
private void dropTable(int m, int n, String[][] table) {
for (int col = 0; col < n; col++) {
for (int row = m - 1; row >= 0; row--) {
if (table[row][col].equals(".")) {
for (int notDotRow = row - 1; notDotRow >= 0; notDotRow--) {
if (!table[notDotRow][col].equals(".")) {
table[row][col] = table[notDotRow][col];
table[notDotRow][col] = ".";
break;
}
}
}
}
}
}
}
buildTable()
에서 일차원 배열의board
를 이차원 배열로 만들었다.- 반복문을 돌며
countFourBlock()
을 통해 지울 수 있는 block의 수를 계산 후, 전체 count에 더해주고dropTable()
을 통해 지웠다. countFourBlock()
에서 지울 수 있는 block인지 확인하는boolean
이차원 배열을 선언 후,checkFourBlock()
을 통해그림의 왼쪽 위부터 차례대로 확인했다. 마지막 행과 열은 확인 할 수 없기 때문에 반복문을m-1
,n-1
까지만 돌며 확인했다. 지울 수 있는 block은.
으로 바꿔주었다.dropTable()
에서 element가.
인 칸을 찾은 후에 그 위로.
가 아닌 칸을 찾아서 두 element를 바꿔주었다.
4. 느낀 점
이차원 배열을 왼쪽 위부터 오른쪽 아래까지 차례대로 확인 👉 지울 수 있는 블록이라면 따로 마킹 👉 이차원 배열에서 마킹해놓은 개수를 덧셈 👉 블록들 삭제 👉 지울 수 있는 블록이 없을 때까지 반복
이라는 흐름은 머리로 간단히 그려졌는데, 막상 코드로 구현하려고 할 때 어려움을 느꼈다.
마킹을 어떻게 해야할까? Key, Value로 구현해야하나? 그럼 Entry를 써야하나? 이런 고민들도 있었고,
지울 수 있는 블록들은 어떻게 삭제를 해야할까? 배열에서는 delete하기 어려우니 List를 써야하나? 하는 고민도 있었다.
다른 분이 푼 코드를 보니, 그냥 따로 boolean 타입의 이차원 배열을 선언하여 해결했고
배열은 delete 대신 .으로 바꿔주었다.
어렵다 ㅜㅜ
'Coding Test > Programmers' 카테고리의 다른 글
프로그래머스 - 추석 트래픽(01/23) (java) (0) | 2021.01.23 |
---|---|
프로그래머스 - 압축 (01/11) (java) (0) | 2021.01.11 |
프로그래머스 - 뉴스 클러스터링 (12/10) (java) (0) | 2020.12.10 |
프로그래머스 - 키패드 누르기 (11/18) (java) (1) | 2020.11.18 |
프로그래머스 - 다트게임(11/16) (java) (0) | 2020.11.16 |