반응형
문제 정보는 아래 링크를 확인해주세요!
[블록 게임]
코딩테스트 연습 - 블록 게임
[[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,4,0,0,0],[0,0,0,0,0,4,4,0,0,0],[0,0,0,0,3,0,4,0,0,0],[0,0,0,2,3,0,0,0,5,5],[1,2,2,2,3,3,0,0,0,5],[1,1,1,0,0,0,0,0,0,5]] 2
programmers.co.kr
문제 접근 방법
- 검은색 블록을 놓을 수 있는 도형은 2x3과 3x2 이 두개의 직사각형 범위 안에서 확인이 가능하고,
- 수평으로 긴 직사각형 안에서는 윗칸의 2개의 값이 비어있어야 가능
- 수직으로 긴 직사각형 안에서는 오른쪽과 왼쪽중 한쪽의 블록이 2개가 비어있어야 가능
- 블록 검사는 맵의 왼쪽부터 오른쪽 컬럼까지 한칸씩 이동하며
- 해당 칸의 비어있지 않은 맨 위에 있는 칸부터 시작한다.
- 수평 검사와 수직 검사에 대한 자세한 설명은 아래 그림 참조!
그림 설명

[소스 코드]
package algorithm.programmers;
import java.util.*;
/*
* 2019 카카오 블라인드
* 블록 게임
*
* */
public class Pro42894 {
private static int[][] board;//게임 맵
private static int[] maxRow;//해당 구간중 가장 위에 있는 row 값
private static int len;
//블록의 좌표
private static class Dot {
int x;
int y;
public Dot(int x, int y) {
this.x = x;
this.y = y;
}
}
public static int solution(int[][] Board) {
int answer = 0;
board = Board;
len = board.length;
maxRow = new int[len];
//각 column당 가장 높은 값을 담는다.
for (int i = 0; i < len; i++) setMaxRow(i);
int cnt = 1;
while(cnt>0) {//지울 수 있는 블록이 1개보다 많을 때까지
cnt = 0;
//각 column을 기준으로 수평블록인지 수직블록인지 검사한다.
for (int i = 0; i < len; i++) {
cnt += checkHorizon(i);
cnt += checkVertical(i);
}
answer += cnt;//지워준 블록의 갯수를 결과 값에 추가
}
return answer;
}
//수직으로 긴 블록을 검사
private static int checkVertical(int col) {
if (col+1 >= len) return 0;//현재 컬럼 기준 +1 위치가 맵 밖이라면 종료
int maxR = Math.max(maxRow[col], maxRow[col+1]);//현재컬럼과 현재컬럼+1블록 중 가장 위에있는 블록
if (maxR-2<0 || maxR>=len) return 0;//수직블록이므로 row가 현재기준 -2보다 작거나 maxR이 맵 범위 밖에있으면 안된다.
int zero = 0;//비어있는 블록을 검사
int block = board[maxR][col];//현재 가장 위에있는 블록의 값
ArrayList<Dot> remove = new ArrayList<>();//지워줄 리스트
for (int i = maxR-2; i <= maxR; i++) {//수직블록은 위로 3개를 검사하므로
for (int j = col; j <= col+1; j++) {//수직블록은 옆으로 2개를 검사하므로
if (board[i][j] != 0 && board[i][j] != block) return 0;//0이 아니면서 현재 블록 값과 다를 때,
if (board[i][j] == 0) zero++;//비어있는 블록을 추가
else remove.add(new Dot(i,j));//지워줄 리스트에 블록 위치 추가
}
}
if (zero != 2) return 0;//수직 블록의 비어있는 값이 2개 일 때, 지워줄 수 있다.
for (Dot d : remove) board[d.x][d.y] = 0;//현재 지워지는 블록들의 위치를 0으로 만든다.
setMaxRow(col);//현재 블록들의 maxR을 재설정
setMaxRow(col+1);
return 1;//하나의 블록을 지웠으므로 1 리턴
}
//수평 블록
private static int checkHorizon(int col) {
if (col+2 >= len) return 0;//수평 블록은 옆으로 3개를 검사하므로
int row1 = maxRow[col];
int row2 = maxRow[col+1];
int row3 = maxRow[col+2];
int maxR = Math.max(row1, Math.max(row2, row3));//3개의 column중 가장 위에 있는 row를 확인
int sameRow = 0;//수평 블록은 같은 row가 2개가 있으므로 이를 검사하기 위함
if (row1 == maxR) sameRow++;
if (row2 == maxR) sameRow++;
if (row3 == maxR) sameRow++;
if (sameRow != 2 || maxR-1 < 0 || maxR >= len) return 0;//같은 블록이 2개가 아니거나, maxR이 범위 밖일 경우 종료
int zero = 0;
int block = board[maxR][col];
ArrayList<Dot> remove = new ArrayList<>();
for (int i = maxR-1; i <= maxR; i++) {//수평블록은 위로 2개를 검사
for (int j = col; j <= col+2; j++) {//수평블록은 옆으로 3개를 검사
if (board[i][j] != 0 && board[i][j] != block) return 0;
if (board[i][j] == 0) zero++;
else remove.add(new Dot(i,j));
}
}
if (zero != 2) return 0;
for (Dot d : remove) board[d.x][d.y] = 0;
setMaxRow(col);
setMaxRow(col+1);
setMaxRow(col+2);
return 1;
}
//maxR을 구하는 메서드
private static void setMaxRow(int col) {
int i = 0;
for (i = 0; i < len; i++) {//map의 해당 컬럼의 제일 위부터 0이 아닌 값이 나올 때까지 검사
if (board[i][col] != 0) break;
}
maxRow[col] = i;//0이 아닌 값이 나왔을 때, 해당 인덱스를 maxR에 저장
}
}
[정확성 테스트]

반응형
LIST
'알고리즘 > 연습문제' 카테고리의 다른 글
2020 카카오 블라인드 코딩테스트 - 괄호 변환 (feat. Java) (0) | 2020.05.19 |
---|---|
2020 카카오 블라인드 코딩테스트 - 문자열 압축 (feat. Java) (0) | 2020.05.19 |
2019 카카오 블라인드 코딩테스트 - 매칭 점수 (fea. Java) (1) | 2020.05.16 |
2019 카카오 블라인드 코딩테스트 - 길 찾기 게임 (feat. Java) (0) | 2020.05.16 |
2019 카카오 블라인드 코딩테스트 - 무지의 먹방 라이브 (feat. Java) (0) | 2020.05.15 |
반응형
문제 정보는 아래 링크를 확인해주세요!
[블록 게임]
코딩테스트 연습 - 블록 게임
[[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,4,0,0,0],[0,0,0,0,0,4,4,0,0,0],[0,0,0,0,3,0,4,0,0,0],[0,0,0,2,3,0,0,0,5,5],[1,2,2,2,3,3,0,0,0,5],[1,1,1,0,0,0,0,0,0,5]] 2
programmers.co.kr
문제 접근 방법
- 검은색 블록을 놓을 수 있는 도형은 2x3과 3x2 이 두개의 직사각형 범위 안에서 확인이 가능하고,
- 수평으로 긴 직사각형 안에서는 윗칸의 2개의 값이 비어있어야 가능
- 수직으로 긴 직사각형 안에서는 오른쪽과 왼쪽중 한쪽의 블록이 2개가 비어있어야 가능
- 블록 검사는 맵의 왼쪽부터 오른쪽 컬럼까지 한칸씩 이동하며
- 해당 칸의 비어있지 않은 맨 위에 있는 칸부터 시작한다.
- 수평 검사와 수직 검사에 대한 자세한 설명은 아래 그림 참조!
그림 설명

[소스 코드]
package algorithm.programmers;
import java.util.*;
/*
* 2019 카카오 블라인드
* 블록 게임
*
* */
public class Pro42894 {
private static int[][] board;//게임 맵
private static int[] maxRow;//해당 구간중 가장 위에 있는 row 값
private static int len;
//블록의 좌표
private static class Dot {
int x;
int y;
public Dot(int x, int y) {
this.x = x;
this.y = y;
}
}
public static int solution(int[][] Board) {
int answer = 0;
board = Board;
len = board.length;
maxRow = new int[len];
//각 column당 가장 높은 값을 담는다.
for (int i = 0; i < len; i++) setMaxRow(i);
int cnt = 1;
while(cnt>0) {//지울 수 있는 블록이 1개보다 많을 때까지
cnt = 0;
//각 column을 기준으로 수평블록인지 수직블록인지 검사한다.
for (int i = 0; i < len; i++) {
cnt += checkHorizon(i);
cnt += checkVertical(i);
}
answer += cnt;//지워준 블록의 갯수를 결과 값에 추가
}
return answer;
}
//수직으로 긴 블록을 검사
private static int checkVertical(int col) {
if (col+1 >= len) return 0;//현재 컬럼 기준 +1 위치가 맵 밖이라면 종료
int maxR = Math.max(maxRow[col], maxRow[col+1]);//현재컬럼과 현재컬럼+1블록 중 가장 위에있는 블록
if (maxR-2<0 || maxR>=len) return 0;//수직블록이므로 row가 현재기준 -2보다 작거나 maxR이 맵 범위 밖에있으면 안된다.
int zero = 0;//비어있는 블록을 검사
int block = board[maxR][col];//현재 가장 위에있는 블록의 값
ArrayList<Dot> remove = new ArrayList<>();//지워줄 리스트
for (int i = maxR-2; i <= maxR; i++) {//수직블록은 위로 3개를 검사하므로
for (int j = col; j <= col+1; j++) {//수직블록은 옆으로 2개를 검사하므로
if (board[i][j] != 0 && board[i][j] != block) return 0;//0이 아니면서 현재 블록 값과 다를 때,
if (board[i][j] == 0) zero++;//비어있는 블록을 추가
else remove.add(new Dot(i,j));//지워줄 리스트에 블록 위치 추가
}
}
if (zero != 2) return 0;//수직 블록의 비어있는 값이 2개 일 때, 지워줄 수 있다.
for (Dot d : remove) board[d.x][d.y] = 0;//현재 지워지는 블록들의 위치를 0으로 만든다.
setMaxRow(col);//현재 블록들의 maxR을 재설정
setMaxRow(col+1);
return 1;//하나의 블록을 지웠으므로 1 리턴
}
//수평 블록
private static int checkHorizon(int col) {
if (col+2 >= len) return 0;//수평 블록은 옆으로 3개를 검사하므로
int row1 = maxRow[col];
int row2 = maxRow[col+1];
int row3 = maxRow[col+2];
int maxR = Math.max(row1, Math.max(row2, row3));//3개의 column중 가장 위에 있는 row를 확인
int sameRow = 0;//수평 블록은 같은 row가 2개가 있으므로 이를 검사하기 위함
if (row1 == maxR) sameRow++;
if (row2 == maxR) sameRow++;
if (row3 == maxR) sameRow++;
if (sameRow != 2 || maxR-1 < 0 || maxR >= len) return 0;//같은 블록이 2개가 아니거나, maxR이 범위 밖일 경우 종료
int zero = 0;
int block = board[maxR][col];
ArrayList<Dot> remove = new ArrayList<>();
for (int i = maxR-1; i <= maxR; i++) {//수평블록은 위로 2개를 검사
for (int j = col; j <= col+2; j++) {//수평블록은 옆으로 3개를 검사
if (board[i][j] != 0 && board[i][j] != block) return 0;
if (board[i][j] == 0) zero++;
else remove.add(new Dot(i,j));
}
}
if (zero != 2) return 0;
for (Dot d : remove) board[d.x][d.y] = 0;
setMaxRow(col);
setMaxRow(col+1);
setMaxRow(col+2);
return 1;
}
//maxR을 구하는 메서드
private static void setMaxRow(int col) {
int i = 0;
for (i = 0; i < len; i++) {//map의 해당 컬럼의 제일 위부터 0이 아닌 값이 나올 때까지 검사
if (board[i][col] != 0) break;
}
maxRow[col] = i;//0이 아닌 값이 나왔을 때, 해당 인덱스를 maxR에 저장
}
}
[정확성 테스트]

반응형
LIST
'알고리즘 > 연습문제' 카테고리의 다른 글
2020 카카오 블라인드 코딩테스트 - 괄호 변환 (feat. Java) (0) | 2020.05.19 |
---|---|
2020 카카오 블라인드 코딩테스트 - 문자열 압축 (feat. Java) (0) | 2020.05.19 |
2019 카카오 블라인드 코딩테스트 - 매칭 점수 (fea. Java) (1) | 2020.05.16 |
2019 카카오 블라인드 코딩테스트 - 길 찾기 게임 (feat. Java) (0) | 2020.05.16 |
2019 카카오 블라인드 코딩테스트 - 무지의 먹방 라이브 (feat. Java) (0) | 2020.05.15 |