Study/Algorithm
프로그래머스 (C/C++, Java) 68936 : 쿼드압축 후 개수 세기
hwooo
2025. 1. 15. 12:44
https://school.programmers.co.kr/learn/courses/30/lessons/68936
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr

풀이
주어진 배열을 탐색하다가 셀 내에 모든 값이 같지 않다면 현재 배열을 4등분한다.
이 때 나눠진 배열의 크기와 시작 좌표를 같이 넘겨 작은 단위의 배열을 탐색하며, 이를 재귀로 반복한다.
만약 모든 값이 같다면 현재 셀의 공통적인 값의 개수를 증가시킨다.
C/C++ 코드
#include <string>
#include <vector>
using namespace std;
vector<int> answer(2, 0);
void compress(vector<vector<int>>& arr, int sr, int sc, int n) {
int val = arr[sr][sc];
for (int i = sr; i < sr + n; i++) {
for (int j = sc; j < sc + n; j++) {
if (val != arr[i][j]) {
n /= 2;
compress(arr, sr, sc, n);
compress(arr, sr, sc + n, n);
compress(arr, sr + n, sc, n);
compress(arr, sr + n, sc + n, n);
return;
}
}
}
answer[val]++;
}
vector<int> solution(vector<vector<int>> arr) {
int n = arr.size();
compress(arr, 0, 0, n);
return answer;
}
Java 코드
class Solution {
private int[] answer = {0, 0};
public int[] solution(int[][] arr) {
int n = arr.length;
compress(arr, 0, 0, n);
return answer;
}
private void compress(int[][] arr, int sr, int sc, int n) {
int value = arr[sr][sc];
for (int i = sr; i < sr + n; i++) {
for (int j = sc; j < sc + n; j++) {
if (arr[i][j] != value) {
n /= 2;
compress(arr, sr, sc, n);
compress(arr, sr, sc + n, n);
compress(arr, sr + n, sc, n);
compress(arr, sr + n, sc + n, n);
return;
}
}
}
answer[value]++;
}
}