[프로그래머스] 쿼드압축 개수 세기

October 6, 2023

📖 문제

level2 쿼드 압축 후 개수 세기

✏️ 나의 풀이

처음에 단순히 dfs 문제라고 생각했지만, 어떻게 배열을 균일한 정사각형으로 쪼개야할지 많이 고민했다.

그래서 문제 예시에 있던 그림처럼 진짜 배열을 잘라 재귀함수를 돌렸다.

배열을 잘라 재귀함수

결과값을 담을 변수 answer 선언
dfs 함수 실행
1. 확인해야하는 배열을 함수에 전달
확인해야하는 길이 n을 매개변수이 arr의 길이로 선언
1. 만일 n이 1일 경우 arr[0][0] 을 answer에 저장
checkArea 함수실행
1. 해당 함수는 인자로 받은 배열내부의 값이 전부 같은 값인지 판별
2. 만일, 모든 값이 같으면 true를 반환
3. 그렇지 않으면 false 반환
checkArea 함수의 결과값으로 true가 나온 경우
1. 해당 배열의 가장 처음값(arr[0][0])을 기준으로 answer에 저장
2. return을 선언해 함수 종료
checkArea 함수의 결과값으로 false가 나온 경우
1. 해당 배열을 4개로 쪼개서 재귀함수를 실행

근데, 재열을 잘라 재귀함수를 돌리게 되면 아무래도 배열을 쪼개는 과정에서 시간이 오래 걸릴것 같아 인덱스로 접근하는 방식으로 다시 구현해보았다.

인덱스로 배열에 접근하여 재귀함수

결과값을 담을 변수 answer 선언
dfs 함수 실행
1. 확인해야하는 배열 전달
2. 시작하는 위치(행과 열) 전달
3. 총 검사해야하는 길이 전달
만일 검사해야하는 길이가 1인 경우 전달받은 행과 열의 값을 answer에 저장
1. 이후 함수 종료
checkArea 함수 실행
1. 해당 함수는 인자로 받은 배열과 행과 열 그리고 검사할 길이를 전달
2. 만일, 모든 값이 같으면 true를 반환
3. 그렇지 않으면 false 반환
checkArea 함수의 결과값으로 true가 나온 경우
1. arr[row][col]을 기준으로 answer에 저장
2. return을 선언해 함수 종료
checkArea 함수의 결과값으로 false가 나온 경우
1. 해당 배열의 시작위치를 4개로 나누어 재귀함수 실행

👩‍💻 코드

배열로 구현

const checkArea = (arr)=>{
    const checkNum = arr[0][0];
    for(let i = 0; i< arr.length; i++){
        for(let j = 0; j<arr[i].length; j++){
            if(arr[i][j]!==checkNum) return false;
        }
    }
    return true;
}
function solution(arr) {
    var answer = [0,0];
    const bfs = (array) =>{
        const n = array.length;
        if(n === 1){
            answer[array[0][0]] += 1;
            return;
        }
        const isSame = checkArea(array);
        if(isSame){
            answer[array[0][0]] += 1;
        }else{
            const arr1 = array.slice(0, n/2).map(v => v.slice(0, n/2));
            const arr2 = array.slice(0, n/2).map(v => v.slice(n/2));
            const arr3 = array.slice(n/2).map(v => v.slice(0, n/2));
            const arr4 = array.slice(n/2).map(v => v.slice(n/2));
            bfs(arr1)
            bfs(arr2)
            bfs(arr3)
            bfs(arr4)
        }
    }
    bfs(arr)
    return answer;
}

인덱스로 접근하여 구현

const checkArea = (arr, row, col, n) =>{
    const checkNum = arr[row][col];
    for(let i = row; i < row+n; i++){
        for(let j = col; j< col+n; j++){
            if(arr[i][j]!==checkNum) return false;
        }
    }
    return true;
}
function solution(arr){
    const answer = [0, 0];
    const bfs = (row, col, n) =>{
        if(n===1){
            answer[arr[row][col]] += 1;
            return;
        }
        const isSame = checkArea(arr, row, col, n);
        if(isSame){
            answer[arr[row][col]] += 1;
            return;
        }
        bfs(row, col, n/2);
        bfs(row + n/2, col, n/2);
        bfs(row, col + n/2, n/2);
        bfs(row + n/2, col + n/2, n/2);
       
    }
    bfs(0, 0, arr.length);
    return answer;
}

내 생각과는 다르게 둘의 차이가 크게 존재하지 않았다.

오히려 인덱스로 접근하는게 더 시간이 걸리는 경우가 존재했다.

slice 메소드가 O(n) 이 걸린다고 알고 있다. 그리고 이 배열은 2차원이기에 slice 메소드를 두변 사용해 O(n^2) 시간이 걸림에도 불구하고 인덱스로 접근하는 것과 큰 차이가 존재하지 않았다.

이 부분은 좀 더 공부해봐야할 것같다.

YUN SEO