[프로그래머스] level2. 쿼드압축 후 개수 세기 (자바 JAVA)

[ 문제 ]  [프로그래머스] level2. 쿼드압축 후 개수 세기 (자바 JAVA)

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/68936

코딩테스트 연습 - 쿼드압축 후 개수 세기

---

# 접근 방법 및 풀이 

 

• 다른 사람 풀이 보니까 재귀로 많이 풀었던데 난 반복문으로 그대로 구현했다.
• 먼저 이차원 배열 map[][]을 생성해 파라미터인 arr을 복사했다. 그냥 arr사용해도 되지만, map을 계속해서 사이즈를 변경해 새로 생성해줄 것이다.
• 2^n 형태이므로, 예를들어 arr의 길이가 8이라면, 8X8 -> 4X4 -> 2X2 -> 1X1 형태로 반복문을 돌며 map의 사이즈를 줄여 생성할 것이다.
• 이차원 map을 이중 for문 돌려 탐색할 때 i+=2, j+=2 씩 2칸 씩 살펴본다.

• 0	1	0	0
  0	0	0	0
  1	1	0	0
  1	1	0	0

• 파란색 글씨로 표시한 인덱스로  i, j 값이 바뀔 것이고, i, j 기준 오른쪽, 오른쪽 아래, 아래를 살펴보며 0과 1의 갯수를 세준다.

• i, j	(i,  j+1)
  (i+1, j)	(i+1, j+1)

• 이렇게 4칸씩 살펴보며, 4칸 모두 0이면 List에 0을 모두 1이면 1을, 그게 아니면 -1을 넣는다.
• 이때 -1일 경우, 0과 1의 갯수를 세서 answer[0]과 answer[1]에 더해준다.
• 그리고 size를 / 2 하여 새로 map을 size크기 만큼 생성해주고, list값을 하나씩 get해 채워준다.

• 0	1	0	1
  0	1	0	1
  0	0	1	1
  0	0	1	1

• -1	-1
  0	1

• -1

• 따라서 map은 4X4 -> 2X2 -> 1X1 형태로 사이즈가 바뀐다.
• 이렇게 size가 1일 경우 마지막 한칸의 값이 뭔지 확인하고 더해주면 된다.
• 자세한건 코드참조

# 주의할 점 

 

• 딱히 없음

 

JAVA 코드

import java.util.*;
class Solution {
    static int dr[] = {0, 1, 1};
	static int dc[] = {1, 1, 0};
	public int[] solution(int[][] arr) {
        int[] answer = new int[2];
        int size = arr.length;
        if(size == 1) {
        	answer[1] = (arr[0][0]==1)? 1 : answer[0]++;
        	return answer;
        }
        int map[][] = new int [size][size];
        for (int i = 0; i < size; i++) {
			map[i] = arr[i].clone();
		}
        while(true) {   	
        	List<Integer> list = new ArrayList<Integer>();
        	for (int i = 0; i < map.length; i+=2) {
        		for (int j = 0; j < map.length; j+=2) {
        			int zero = 0;
        			int one = 0;
        			if(map[i][j] == 0 || map[i][j] == 1)
        				zero = (map[i][j]==0)? 1 : one++;
					for (int d = 0; d < 3; d++) {
						int n = map[i+dr[d]][j+dc[d]];
						if(n == -1)
							continue;
						if(n == 0)
							zero++;
						else
							one++;		
					}
					if(zero == 4 || one == 4) {
						list.add(map[i][j]);
					}else {
						list.add(-1);
						answer[0] += zero;
						answer[1] += one;
					}
				}
			}
        	size /= 2;
        	map = new int[size][size];
        	int idx = 0;
        	for (int i = 0; i < map.length; i++) {
				for (int j = 0; j < map.length; j++) {
					map[i][j] = list.get(idx);
					idx++;
				}
			}
            if(size == 1) {
        		if(map[0][0] != -1)
        			answer[1] = (map[0][0]==1)? 1 : answer[0]++;
        		break;
        	}
        }
        return answer;
    }
}

REVIEW