처음 풀이
1. 삭제할 블록 체크
2. 블록 삭제
3. 블록 이동
이 세 과정을 더 이상 삭제할 블록이 없을 때까지 반복하면 된다.
//각 글자를 요소로 할 2차원 배열
char[][] gameBoard;
//사이클마다, 삭제할 2x2 블록의 첫 번째 원소의 좌표 담을 set
Set<int[]> set = new HashSet<>();
//삭제되는 블록의 갯수
int count;
public int solution(int m, int n, String[] board) {
//m x n 사이즈의 2차원 배열 생성
gameBoard = new char[m][n];
//게임 보드 알파벳 채우기
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
gameBoard[i][j] = board[i].charAt(j);
}//for end
}//for end
while(true) {
//삭제할 블록 있는지 체크(set에 블록 좌표 add)
check(m, n);
if(!set.isEmpty()) {
//삭제할 블록 있는 경우
//해당 위치의 배열 요소 값 ' ' 으로 초기화
delete();
//삭제된 블록 자리 메꾸기
move(m, n);
} else {
//더 이상 삭제할 블록이 없는 경우
break;
}//if~else end
}//while end
return count;
}//solution() end
1. 삭제할 블록 체크
- gameBoard 탐색하면서 [i][j], [i][j+1], [i+1][j], [i+1][j+1] 위치 값이 다 같다면 set에 int 배열로 {i, j}를 저장한다.
public static void check(int m, int n) {
//매 사이클마다 set 초기화해준다.
set.clear();
for (int i = 0; i < m-1; i++) {
for (int j = 0; j < n-1; j++) {
//사이클이 돌아 빈 블록인 경우
//continue
if(gameBoard[i][j]==' ') continue;
if(gameBoard[i][j]==gameBoard[i][j+1]
&& gameBoard[i][j]==gameBoard[i+1][j]
&& gameBoard[i][j]==gameBoard[i+1][j+1]) {
set.add(new int[]{i, j});
}//if end
}//for end
}//for end
}//check() end
2. 블록 삭제
set에 있는 대표 좌표를 중심으로 4좌표 모두 초기화한다.
블록들끼리 겹치는 부분을 조심해서 count한다.
public static void delete() {
Iterator<int[]> iterator = set.iterator();
while(iterator.hasNext()) {
int[] location = iterator.next();
//2x2블록의 대표 좌표 중심으로 4좌표 모두 ' '로 초기화
//블록들이 겹치는 부분은 한 번만 카운트 한다.
if(gameBoard[location[0]][location[1]]!=' ') {
gameBoard[location[0]][location[1]] = ' ';
count++;
}
if(gameBoard[location[0]][location[1]+1]!=' ') {
gameBoard[location[0]][location[1]+1] = ' ';
count++;
}
if(gameBoard[location[0]+1][location[1]]!=' ') {
gameBoard[location[0]+1][location[1]] = ' ';
count++;
}
if(gameBoard[location[0]+1][location[1]+1]!=' ') {
gameBoard[location[0]+1][location[1]+1] = ' ';
count++;
}
}//while end
}//delete() end
3. 남은 블록 이동
아랫줄에서부터 빈 블럭을 채워나간다.
public static void move(int m, int n) {
//아래서부터 채워야 하므로 마지막 row부터 탐색
for (int i = m-1; i >= 0; i--) {
for (int j = 0; j < n; j++) {
if(gameBoard[i][j]==' ') {
//빈 블록일 때
//현재 위치[i][j]서부터 위로 올라가면서
//비지 않은 블록의 값으로 현재 위치의 블록을 채우고
//값을 가져온 블록은 ' '로 비운다.
for (int k = i; k >= 0 ; k--) {
if(gameBoard[k][j]!=' ') {
gameBoard[i][j] = gameBoard[k][j];
gameBoard[k][j] = ' ';
break;
}//if end
}//for end
}//if end
}//for end
}//for end
}//move() end
다른 풀이
Set을 활용하여 삭제할 2x2 블록의 대표 좌표가 아닌 모든 좌표를 Point 클래스의 객체로 저장한다.
HashSet이, Point의 row와 column 필드값이 같다면 같은 Point 객체로 판단할 수 있도록 hashcode()와 equals()를 오버라이딩 해준다.
따라서, 중복된 좌표는 Set에 두 번 저장하지 않는다.
Point 클래스
static class Point {
int row;
int column;
public Point(int row, int column) {
this.row = row;
this.column = column;
}
@Override
public boolean equals(Object obj) {
if(obj instanceof Point) {
Point point = (Point) obj;
return (point.row == this.row)
&& (point.column == this.column);
} else {
return false;
}
}
@Override
public int hashCode() {
return Objects.hash(row, column);
}
}
check()
- 삭제할 모든 블록의 좌표(Point)를 Set에 저장한다.
pointSet.add(new Point(i, j));
pointSet.add(new Point(i, j+1));
pointSet.add(new Point(i+1, j));
pointSet.add(new Point(i+1, j+1));
solution()
- 매 사이클마다 Set의 사이즈가 곧 삭제된 블록의 갯수이다.
while(true) {
check(m, n);
if(!set.isEmpty()) {
//set의 사이즈 = 삭제할 블록 갯수
count += set.size();
delete();
move(m, n);
} else {
break;
}//if~else end
}//while end
delete()
- 삭제할 모든 블록이 Set에 저장되어있다.
while(iterator.hasNext()) {
Point point = iterator.next();
gameBoard[point.row][point.column] = ' ';
}//while end
'자료구조 & 알고리즘 > 문제풀이' 카테고리의 다른 글
[3차] 압축 - 2018 KAKAO (Java, Level 2) (0) | 2022.03.25 |
---|---|
후보키 - 2019 KAKAO BLIND RECRUITMENT (Java, Level 2) (0) | 2022.03.22 |
튜플 - 프로그래머스 (Java, level 2) (0) | 2022.03.16 |
오픈채팅방 - 프로그래머스 (Java, Level 2) (0) | 2022.03.15 |
단체 사진찍기 - 프로그래머스 (Java, Level 2) (0) | 2022.03.14 |
댓글