🔎 프렌즈4블록
❓ 문제링크
https://programmers.co.kr/learn/courses/30/lessons/17679
📄 제출 코드
// 해야될거
// 4각형되면 제거하기.
// how?
// 3방향 탐색.
//
// 그리고?
// 빈공간 내리기
//
// 언제까지?
// 위작업을 했을 때 전과 후가 똑같을때까지.
function solution(m, n, board) {
var answer = 0;
let prevMap = board.map((el) => el.split(''));
let curMap = board.map((el) => el.split(''));
console.log('start')
console.log(curMap);
while (true) {
console.log('prev')
console.log(prevMap)
goDelete(m, n, prevMap, curMap);
console.log('delete')
console.log(curMap)
moveMap(m, n, prevMap, curMap);
console.log('move')
console.log(curMap);
console.log(prevMap);
if (sameMap(m, n, prevMap, curMap)) { break; }
else {
copyMap(m,n,prevMap, curMap);
}
}
answer = countMap(m, n, curMap);
return answer;
}
// 3방향 우 우하 하
let dx = [0, 1, 1];
let dy = [1, 1, 0];
function goDelete(m, n, prevMap, curMap) {
for (let i = 0; i < m - 1; i++) {
for (let j = 0; j < n - 1; j++) {
deleteMap(i, j, prevMap, curMap);
}
}
}
function deleteMap(x, y, prevMap, curMap) {
let [cx, cy] = [x, y];
let cnt = 0;
let tmp = [];
for (let i = 0; i < 3; i++) {
let nx = x + dx[i];
let ny = y + dy[i];
if (prevMap[cx][cy] == prevMap[nx][ny]) {
cnt++;
tmp.push([nx, ny]);
if (cnt == 3) {
curMap[cx][cy] = '0';
for (let i = 0; i < 3; i++) {
let tx = tmp[i][0];
let ty = tmp[i][1];
curMap[tx][ty] = '0';
}
}
} else {
cnt = 0;
tmp.splice(0);
break;
}
}
console.log('indelete')
console.log(prevMap);
}
function moveMap(m, n, prevMap, curMap) {
console.log('inmethod b')
console.log(prevMap)
for (let i = m - 1; i > 0; i--) {
for (let j = 0; j < n; j++) {
if (curMap[i][j] == '0') {
for (let k = i - 1; k >= 0; k--) {
if (curMap[k][j] != '0') {
curMap[i][j] = prevMap[k][j];
curMap[k][j] = '0'
break;
}
}
}
}
}
console.log('inmethod a')
console.log(prevMap)
}
function sameMap(m, n, prevMap, curMap) {
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (prevMap[i][j] != curMap[i][j]) return false;
}
}
return true;
}
function copyMap(m, n, prevMap, curMap) {
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
prevMap[i][j] = curMap[i][j]
}
}
}
function countMap(m, n, prevMap) {
let cnt = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (prevMap[i][j] == '0') cnt++;
}
}
return cnt;
}
// let m = 8;
// let n = 5;
// let board =["HGNHU", "CRSHV", "UKHVL", "MJHQB", "GSHOT", "MQMJJ", "AGJKK", "QULKK"]
// console.log(solution(m,n,board))
// base(edge) Condition
// console.log(solution(2, 2, ["AA", "AA"])) // 4
// console.log(solution(2, 2, ["AA", "AB"])) //0
// 블록제거
// console.log(solution(3, 2, ["AA", "AA", "AB"])) // 4
// console.log(solution(4, 2, ["CC", "AA", "AA", "CC"])) //8
// 블록내리기
console.log(solution(6, 2, ["DD", "CC", "AA", "AA", "CC", "DD"])) //12
// console.log(solution(8, 2, ["FF", "AA", "CC", "AA", "AA", "CC", "DD", "FF"])) // 8
// console.log(solution(6,2, ["AA", "AA", "CC", "AA", "AA", "DD"])) // 8구현문제인데 중간에 2번 꼬여가지고 되게 오래걸렸다.
어제 풀기 시작했는데 처음엔 testcase입력부분에 board를 [["CCBDE", "AAADE", "AAABF", "CCBBF"]]이런 식으로 작성이 되서 애초에 다 꼬여서 다 실패가 떳다.
(자동완성조심!)
두 번째는 작성하다가 curMap prevMap이 제대로 안바껴서 고치다가 꼬여가지고, 오늘로 문제를 넘겼다.
오늘은 여태작성한걸 다 지우고, 차근차근 작성해나갔다.
// 해야될거
// 4각형되면 제거하기.
// how?
// 3방향 탐색.
//
// 그리고?
// 빈공간 내리기
//
// 언제까지?
// 위작업을 했을 때 전과 후가 똑같을때까지.우선 어떻게 작성해나갈지부터 작성했다.
그 후 작성할 메소드를 한개씩 만들어 나갔다.
1. 3방향 탐색을 통해 4각형을 제거하는 deleteMap 메소드
2. 아래로 이동시키는 moveMap 메소드
3. 이전 Map과 비교해서 같은지 확인할 sameMap 메소드
4. 0의 개수를 셀 countMap 메소드
5. prevMap을 curMap으로 복사하는 copyMap 메소드.
👉 deleteMap()
모든 좌표를 돌면서 3방향탐색을 하고, 3방향탐색에서 같은 글자가 있으면 tmp에 해당좌표를 저장하고, 3개다 같은 글자면 tmp좌표의 curMap을 0으로 바꾼다.
중간에 글자가 다른 경우가 있으면 사각형은 안되기 때문에 바로 tmp와 cnt를 초기화시키고 break한다.
function deleteMap(x, y, prevMap, curMap) {
let [cx, cy] = [x, y];
let cnt = 0;
let tmp = [];
for (let i = 0; i < 3; i++) {
let nx = x + dx[i];
let ny = y + dy[i];
if (prevMap[cx][cy] == prevMap[nx][ny]) {
cnt++;
tmp.push([nx, ny]);
if (cnt == 3) {
curMap[cx][cy] = '0';
for (let i = 0; i < 3; i++) {
let tx = tmp[i][0];
let ty = tmp[i][1];
curMap[tx][ty] = '0';
}
}
} else {
cnt = 0;
tmp.splice(0);
break;
}
}
}👉 moveMap()
처음엔 외에서부터 한칸씩 내려나가는 방법으로 했는데 이러면 제대로 이동을 안하게 된다.
첫번째 테스트케이스경우 오른쪽 두번째줄에 00DD가되야하는데 D00D로 끝나게된다.
그래서 아래서부터 위로 올라가면서 이동시키는 방법을 사용했다.
function moveMap(m, n, prevMap, curMap) {
for (let i = m - 1; i > 0; i--) {
for (let j = 0; j < n; j++) {
if (curMap[i][j] == '0') {
for (let k = i - 1; k >= 0; k--) {
if (curMap[k][j] != '0') {
curMap[i][j] = prevMap[k][j];
curMap[k][j] = '0'
break;
}
}
}
}
}
}👉 sameMap()
단순히 반복돌면서 curMap과 prevMap이 같은지 비교하여 true false를 리턴한다.
function sameMap(m, n, prevMap, curMap) {
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (prevMap[i][j] != curMap[i][j]) return false;
}
}
return true;
}👉 countMap()
0을 세는 메소드로 0을 세서 0의 수를 리턴하여 답을 도출함.
function countMap(m, n, prevMap) {
let cnt = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (prevMap[i][j] == '0') cnt++;
}
}
return cnt;
}👉 copy
처음에 배열을 sameMap이 false일 때, Array.from으로 prevMap을 curMap으로 복사했는데,
testCase 5, 6, 10, 11이 계속 틀렸다.
질문게시판에서 반례를 찾아서 다입력해보고, 과정마다 map을 출력하면서 비교해봤다.
console.log(solution(6, 2, ["DD", "CC", "AA", "AA", "CC", "DD"])) //12
위 테케에서 답이 8로 반례가 나왔고, 이동하는 과정에서 prevMap이 갑자기 변하는 경우가 발생했다.
처음부터 틀린게 아니라서 뭐지 하다가 1시간반동안의 삽질 후 복사할때 뭐가 잘못된건가 싶어 copyMap()이란 메소드를 만들어 하나하나 바꾸니까 통과했다.
Array.from은 얕은 복사라서 그런듯 하다. 깊은 복사의 방법을 찾아보니 JSON.parse()가 있어서 JSON.parse를 이용해 prevMap을 curMap으로 복사하니 통과하였다.
