💡 문제
https://school.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가 사용된다.
출력 형식
입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.
내 풀이
function solution(m, n, board) {
var arr = [];
var boardArr = [];
var index = 0;
var answer = 0;
board.forEach((v)=>boardArr.push(v.split(""))); // 2차원 배열로 변환
while(true){
for(let i = 0; i < m-1; i++){
for(let j = 0; j < n; j++){
if(boardArr[i][j]!==0 &&
boardArr[i][j]===boardArr[i][j+1]&&
boardArr[i][j+1]===boardArr[i+1][j]&&
boardArr[i+1][j]===boardArr[i+1][j+1]
){
arr.push([i,j],[i,j+1],[i+1,j],[i+1,j+1]);
// 터뜨릴 블록의 index를 arr에 넣음
}
}
}
if(arr.length===0) break; // 더이상 터뜨릴 블록이 없다는 뜻이므로 break
arr.forEach((v)=>boardArr[v[0]][v[1]]=0); // 터뜨릴 블록을 0으로 바꿔줌
arr = []; // arr 초기화
for(let i = 1; i < m; i++){
for(let j = 0; j < n; j++){
if(boardArr[i][j]===0){ // 터진 블록이라면
boardArr[i][j]=boardArr[i-1][j]; // 0 자리에 위의 블록 값을 넣음(블록이 아래로 떨어짐)
if(i-2>=0 && boardArr[i-2][j]!==0){
index = i;
while(index-2 >= 0){
boardArr[index-1][j]=boardArr[index-2][j];
boardArr[index-2][j]=0;
index--;
}
}else{
boardArr[i-1][j]=0; // 떨어진 블록 자리를 0으로 채움
}
}
}
}
}
for(let i = 0; i < m; i++){
for (let j = 0; j < n; j++){
if(boardArr[i][j]===0){
answer++; // 0의 개수 (터진 블록 개수) 세기
}
}
}
return answer;
}이게 뭐라고 거의 5시간? 6시간 쓴 듯.. 아니 더 썼을수도..
이거 정답률이 48%라던데 저는 카카오 못가겠습니다..ㅋㅋㅋㅋㅋㅋㅋ
- 먼저 배열의 문자열을 2차원 배열로 나눕니다.
- 배열에서 지워질 블록의 인덱스를 구해 arr안에 넣습니다.
- 배열에서 지워질 블록을 0으로 바꿉니다.
- 깨진 블록을 없애고 위에서 블록을 당겨옵니다. (이 부분의 로직이 어려운데 먼저 위에서 가져올 블록이 있는지 검사합니다.)
https://kyun2da.github.io/2020/07/05/friendsblock/
여기서 본 힌트로 감을 잡고 삽질해서 겨우 풀었다.
테스트케이스 5번에서만 자꾸 틀리길래 테스트케이스 이것저것 집어넣어봤는데 8, 5, ["HGNHU", "CRSHV", "UKHVL", "MJHQB", "GSHOT", "MQMJJ", "AGJKK", "QULKK"] 8 여기서 막히길래 콘솔 찍어봤더니 아래쪽에서 터진 블록 자리를 위에서부터 내려오면서 매꿔야 하는데 바로 위의 2칸만 내려오고 그 위의 블럭들은 안내려와서 실패한 거였다!
ex)
...
VL
QB // 여기서부터 안내려옴!
00
00
OT
JJ index = i;
while(index-2 >= 0){
boardArr[index-1][j]=boardArr[index-2][j];
boardArr[index-2][j]=0;
index--;
}그래서 while문 돌면서 가장 위에있는 블록들도 내리게 해줬더니 테스트 5번을 통과했다!!
다른 사람 풀이
function solution(m, n, board) {
board = board.map(v => v.split(''));
while (true) {
let founded = [];
// 찾기
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (board[i][j] && board[i][j] === board[i][j - 1] && board[i][j] === board[i - 1][j - 1] && board[i][j] === board[i - 1][j]) {
founded.push([i, j]);
}
}
}
if (! founded.length) return [].concat(...board).filter(v => ! v).length;
// 부수기
founded.forEach(a => {
board[a[0]][a[1]] = 0;
board[a[0]][a[1] - 1] = 0;
board[a[0] - 1][a[1] - 1] = 0;
board[a[0] - 1][a[1]] = 0;
});
// 재정렬
for (let i = m - 1; i > 0; i--) {
if (! board[i].some(v => ! v)) continue;
for (let j = 0; j < n; j++) {
for (let k = i - 1; k >= 0 && ! board[i][j]; k--) {
if (board[k][j]) {
board[i][j] = board[k][j];
board[k][j] = 0;
break;
}
}
}
}
}
}왤케 천재들이 많아....
