programmers. 프렌즈 4블록

문제

문제

코딩테스트 연습 - [1차] 뉴스 클러스터링

풀이

처음에는 2차원 배열을 dfs로 돌면서 체크한 뒤에 지우려고 했는데 도저히 이렇게 접근해서는 지울 방법도, 순회도 답이 안나와서 다른 사람의 풀이를 봤다

2차원 배열을 순회하며 원소로 들어가있는 값들이 모두 대문자인 점에서 2x2를 만족하는 원소들에 대해 소문자로 바꾼다 까지만 보고 감이 좀 잡히는 것 같아서 혼자 풀었다

모든 배열을 순회하면서 좌표를 기준으로 2x2크기만큼 모두 같은 문자인지 확인하고 조건이 맞으면 해당 크기에 있는 문자들을 모두 소문자로 바꾼다

같은 문자인지 확인하는 과정에서 대/소문자는 구분하지 않는다 (사각형이 겹칠 수 있기 때문)

순회하고 나서 대문자 밑에 소문자가 존재한다면 대문자를 내리는 과정을 반복

대문자를 내리는 과정에서 문제가 좀 있었는데

[A,A]
[B,B]
[B,B]
[A,A]
[B,B]
[B,B]

첫 순회를 돌고 소문자로 바꾸고

[A,A]
[b,b]
[b,b]
[A,A]
[b,b]
[b,b]

대문자를 내려주면

[b,b]
[b,b]
[A,A]
[b,b]
[b,b]
[A,A]

이렇게 된다 내리는 과정중에는 2x2 크기 체크를 해줄 수가 없고 소문자를 내려주는 일을 반복해서 해야할지 어떡할지 고민하다가

첫 줄에서 정방향으로 돌리면서 대문자를 내리는 것이 아니라 마지막 줄에서 대문자를 내리는 식으로 하면 중간에서 멈추지않는다

코드

function solution(m, n, board) {
    var answer = 0;
    const fourDir = [[0,0],[0,1],[1,0],[1,1]];
    board = board.map(v=>v.split(''));
    let changed = false;


    while (true){
        for(let i=0;i<m-1;i++) {
            for (let j = 0; j < n - 1; j++) {
                if(board[i][j]!=='-') checkSides(i, j);
            }
        }
        // console.log(JSON.parse(JSON.stringify(board)));
        if(changed){
            for(let i=m-1;i >=0;i--){
                for(let j=0; j<n;j++){
                    if(board[i][j]>='a'&& board[i][j]<='z') board[i][j] = '-'
                    else down(i,j);
                }
            }
            changed = false;
        } else break;
        // console.log(JSON.parse(JSON.stringify(board)));
    }

    // console.log(answer)
    function down(i, j) {
        for(let k=0; k+i<m-1; k++){
            const char = board[i+k][j];

            if(char>='A' && char<='Z') {
                if(board[i+1+k][j] ==='-'){
                    board[i+k][j] = '-';
                    board[i+1+k][j] = char;
                }
            }
        }
    }

    function checkSides(y, x) {
        const sides = fourDir.map(v=>[v[0]+y,v[1]+x]);
        for(let i =0; i<sides.length;i++){
            const [py,px] = sides[i];
            if(!isSame(board[y][x],board[py][px])) return ;
        }
        change(sides);
    }
    function change(arr){
        arr.forEach(v=>{
            const [y,x] = v;
            if(board[y][x] === board[y][x].toLowerCase()) return ;
            board[y][x] = board[y][x].toLowerCase();
            answer++;
            changed = true;
        });

    }

    return answer;
}



function isSame(char1, char2){
    return char1.toLowerCase() === char2.toLowerCase();
}