https://programmers.co.kr/learn/courses/30/lessons/84021
코딩테스트 연습 - 3주차
[[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0
programmers.co.kr
문제 요약
table[][]에 있는 퍼즐 조각을 game_board[][]에 최대한으로 채워넣을 수 있는 칸의 개수 리턴
* 퍼즐 회전 가능 ( 뒤집을 수는 없음 )
* 채워 넣은 퍼즐 조각과 인접한 칸이 비어 있으면 안 됨
* game_board의 가로 길이 = game_board의 세로길이 = table의 가로 길이 = table의 세로 길이
문제 풀이
import java.util.*;
public class Solution {
class Cell {
int x, y;
Cell(int x, int y) {
this.x = x;
this.y = y;
}
}
public List<boolean[][]> findBlocks(int[][] a, int o, int n) { /* BFS */ // a : array, o : value (zero or one), n : length of board
int i, j, d, x, y, nx, ny; // d : direction, x/y : [next] x/y
int dx[] = { 0, 1, 0, -1 }, dy[] = { 1, 0, -1, 0 }; // directions x/y
boolean v[][] = new boolean[n][n]; // v : array to check visited cells
List<boolean[][]> bs = new ArrayList<>(); // blocks
List<Cell> b; // one block
Queue<Cell> q; Cell c, nc; // q : queue, c : [next] cell
for (i = 0; i < n; ++i) {
for (j = 0; j < n; ++j) {
if (a[i][j] == o && !v[i][j]) {
b = new ArrayList<>();
q = new ArrayDeque<>();
c = new Cell(i, j);
b.add(c);
q.add(c);
v[i][j] = true;
while (!q.isEmpty()) {
c = q.remove();
x = c.x; y = c.y;
for (d = 0; d < 4; ++d) {
nx = x + dx[d]; ny = y + dy[d];
if ((nx >= n || ny >= n || nx < 0 || ny < 0) || v[nx][ny])
continue;
if (a[nx][ny] == o) {
nc = new Cell(nx, ny);
b.add(nc);
q.add(nc);
v[nx][ny] = true;
}
}
}
bs.add(getBlockArr(b, n));
}
}
}
return bs;
}
public boolean[][] getBlockArr(List<Cell> b, int n) { // b : block
int x, y, mx = n, my = n; // mx/my : minimum val of x/y
for (Cell c : b) { // c : cell
x = c.x; y = c.y;
mx = mx > x ? x : mx;
my = my > y ? y : my;
}
int m = 0; // m : max length of the block
for (Cell c : b) { // c : cell
c.x -= mx;
c.y -= my;
x = c.x; y = c.y;
m = m < x ? x : m;
m = m < y ? y : m;
}
m++;
boolean bb[][] = new boolean[m][m];
for (Cell c : b)
bb[c.x][c.y] = true;
return bb;
}
public int getBlockSize(boolean[][] b, int m) { // b : block, m : max length of the block
int s = 0, i, j;
for (i = 0; i < m; ++i)
for (j = 0; j < m; ++j)
if (b[i][j])
s++;
return s;
}
public boolean[][] rotateBlock(boolean[][] b, int m) { // b : block, m : max length of the block
int mx = m, my = m, i, j;
boolean bb[][] = new boolean[m][m];
for (i = 0; i < m; ++i) {
for (j = 0; j < m; ++j) {
bb[i][j] = b[m - j - 1][i];
if (bb[i][j]) {
mx = mx > i ? i : mx;
my = my > j ? j : my;
}
}
}
boolean bbb[][] = new boolean[m][m];
for (i = 0; i < m; ++i)
for (j = 0; j < m; ++j)
if (bb[i][j])
bbb[i-mx][j-my] = true;
return bbb;
}
public boolean isSame(boolean[][] b1, boolean[][] b2, int m) { // b : block, m : max length of the block
int i, j;
for (i = 0; i < m; ++i)
for (j = 0; j < m; ++j)
if( b1[i][j] != b2[i][j] )
return false;
return true;
}
public int solution(int[][] game_board, int[][] table) {
int ans = 0, n = game_board.length, m, k; // n : length of board, m : max length of the block
List<boolean[][]> bs_b = findBlocks(game_board, 0, n), bs_t = findBlocks(table, 1, n); // bs_b/t : blocks_board/table
Map<Integer, List<boolean[][]>> map_b = new TreeMap<>();
Map<Integer, List<boolean[][][]>> map_t = new TreeMap<>(); boolean[][][] b_r; // b_r : block_rotated
for (boolean[][] b : bs_b) {
m = b.length;
if (!map_b.containsKey(m))
map_b.put(m, new ArrayList<>());
map_b.get(m).add(b);
}
for (boolean[][] b : bs_t) {
m = b.length;
b_r = new boolean[4][m][m];
b_r[0] = b;
for (k = 1; k <= 3; ++k) {
b = rotateBlock(b, m);
b_r[k] = b;
}
if (!map_t.containsKey(m))
map_t.put(m, new ArrayList<>());
map_t.get(m).add(b_r);
}
List<boolean[][][]> puzzles; int s; // s : size of the block
for (int mm : map_b.keySet()) { // mm : max length of the block
loop:
for (boolean[][] space : map_b.get(mm)) { // space : empty space( block ) of the board
puzzles = map_t.get(mm);
if (puzzles == null)
continue;
s = getBlockSize(space, mm);
for (boolean[][][] puzzle_r : puzzles) {
for (boolean[][] puzzle : puzzle_r) { // puzzle : puzzle of the table
if (isSame(space, puzzle, mm)) {
ans += s;
puzzles.remove(puzzle_r);
continue loop;
}
}
}
}
}
return ans;
}
}
[ 변수명 설명 ]
ex)
- cell : 한 칸
- block : 인접한 cell들의 한 블록
- space : game_board[][] 에서의 한 블록
- puzzle : table[][] 에서의 한 블록
[ 함수 설명 ]
- findBlocks() : 각 블록의 좌표들을 구함 ( spaces, puzzles 각각 )
- game_board[][] 에서는 빈공간( game_board[i][j] == 0 인 { i, j } 로부터 BFS )을 찾고,
table[][] 에서는 퍼즐 조각( table[i][j] == 1 인 { i, j } 로부터 BFS )을 찾아
그 좌표들( x, y 좌표로 구성된 Cell class의 List )를 List에 넣음 ( List<Cell> b ) - 이 때 위치( x, y 좌표 ) 그대로가 아니라 기본형 배열로 바꾼 후 넣음 ( boolean[][] )
- 퍼즐들의 각 좌표 배열을 담은 리스트 리턴 ( List<boolean[][]> bs )
ex) 위의 '그림 1'에서
■ 노란색 space 블럭의 좌표들은 [[3,2],[4,1],[4,2],[4,3]]
■ 초록색 puzzle 블럭의 좌표들은 [[2,1],[1,2],[2,2],[3,2]]
- getBlockArr() : 한 블록의 좌표들의 리스트( List<Cell> b )를 전달 받아 기본형 배열( boolean[][] b )을 리턴함
( 기본형이라는 것은 블록의 위치에 상관 없이 같은 블록인지 비교할 수 있게끔 전처리 한 것을 의미 )
- 한 블록을 구성하는 셀의 좌표들에서 x, y의 각각의 최솟값( int mx, my )을 구하여 좌표값에서 뺌
- 가로 세로 통틀어 가장 큰 값( int m )을 구해 정사각형 모양의 퍼즐 배열 생성
ex) 위의 '그림 1'에서
■ 노란색 블럭의 기본형 좌표들은 [[0,1],[1,0],[1,1],[1,2]] ( mx는 3, my는 1 )
■ 초록색 블럭의 기본형 좌표들은 [[0,1],[1,0],[1,1],[2,1]] ( mx는 1, my는 1 )
- rotateBlock() : 한 블록( boolean[][] b )을 90도로 회전하고 좌표들의 기본형을 구함
- boolean bb[][] 2차원 배열을 새로 생성함( 가로&세로 길이는 블록에서 가장 긴 길이( int m )가 됨 )
- 그 2차원 배열을 90도로 회전( boolean[][] bb ) 후 기본형 배열( boolean[][] bbb )로 만듦
ex) 위의 '그림 1'에서
■ 초록색 블럭을 90도로 회전한 블록의 기본형 좌표들은 [[0,1],[1,0],[1,1],[1,2]]
ex) 다른 예로 [[0,3],[1,3],[2,0],[2,1],[2,2],[2,3]] 로 구성된 블록
■ 회색 블럭을 90도로 회전한 블록의 기본형 좌표들은 [[0,0],[1,0],[2,0],[3,0],[3,1],[3,2]]
- isSame() : 입력받은 두 블록의 모양이 일치하는지 판단
- 두 블록을 구성하는 좌표 배열의 값이 모두 같으면 두 블록은 모양이 일치함
ex) 위의 '그림 1'에서
■ 노란색 블럭의 모양과 ■ 초록색 블럭을 90도로 회전한 블록의 모양이 일치함
- solution()
- game_board[][] 에서 findBlocks()를 통해 spaces( blocks )들을 구한 것을 담은 List<boolean[][]> bs_b,
table[][] 에서 findBlocks()를 통해 puzzles( blocks )들을 구한 것을 담은 List<boolean[][]> bs_t 을 생성 - Map<Integer, List<boolean[][]>> map_b 생성 후, bs_b 탐색하며 한 변의 길이가 m( key )인 블록들( value )를 담고,
Map<Integer, List<boolean[][][]>> map_t 생성 후, bs_t 탐색하며 한 변의 길이가 m( key )인 블록들( value )
( + rotateBlock() 로 회전한 모양 포함 ) 를 담음 - map_b을 탐색하면서 한 space( block )에 대해 map_t을 탐색하며 puzzle( block ) 하나 당 3번 회전 시킨 총 4개의 모양을 isSame() 함수를 통해 비교하고, 일치하면 ans += s ( 블록의 칸 수 )
ex) 위의 '그림 1'에서
색칠된 board, table에서의 각각의 block( ■ space, ■ puzzle )에 대해 map_b, map_t에 각각 넣은 결과
'코딩 문제 풀기 ( Algorithm problem solving ) > 프로그래머스 ( Programmers )' 카테고리의 다른 글
[프로그래머스(Programmers)][자바(java)] (Lv2) 5주차 - 모음 사전 <위클리 챌린지> (0) | 2021.09.01 |
---|---|
[프로그래머스(Programmers)][자바(java)] (Lv1) 4주차 - 직업군 추천하기 <위클리 챌린지> (0) | 2021.08.26 |
[프로그래머스(Programmers)][자바(java)] (Lv1) 2주차 - 상호 평가 <위클리 챌린지> (0) | 2021.08.26 |
[프로그래머스(Programmers)][자바(java)] (Lv1) 1주차 - 부족한 금액 계산하기 <위클리 챌린지> (0) | 2021.08.26 |
[프로그래머스(Programmers)][자바(java)] (Lv2) 이진 변환 반복하기 <월간 코드 챌린지 시즌1> (0) | 2021.07.12 |