2026.07.01
문제 풀이
1차 실행 오류
0.0/100
import java.util.Map;
import java.util.HashMap;
class Solution {
public int[] solution(int[][] arr) {
Map<Integer, Integer> blocks = new HashMap<>();
Map<Integer, Boolean> possible = new HashMap<>();
Map<Integer, int[]> compaction = new HashMap<>(); // key: 블록의 사분면, value: [영역의 크기, 0의 개수, 1의 개수]
int len = arr.length;
int dividend = len;
boolean bool[][] = new boolean[len][len];
while(true) {
if (dividend == 1) {
break;
}
int block = 0; // 현재 속한 블록의 위치
for (int row = 0; row < len; row++) {
if (row % dividend == 0) {
block = block + 1;
if (block > (len / dividend)) {
block = 1;
}
}
for (int col = 0; col < len; col++) {
if (col % dividend == 0) {
if (row % dividend == 0 && col == 0) {
blocks.clear();
blocks.put(block, arr[row][col]);
possible.put(block, true);
}
else if (row % dividend != 0) {
block = block + 1;
if (block > (len / dividend)) {
block = 1;
}
}
else {
block = block + 1;
if (block > (len / dividend)) {
block = 1;
}
blocks.put(block, arr[row][col]);
possible.put(block, true);
}
}
if (arr[row][col] != blocks.get(block)) {
possible.put(block, false);
}
if (row % dividend == dividend - 1 && col % dividend == dividend - 1) { // 한 블록이 끝났을 때
if (possible.get(block) == true) { // 압축 가능할 때
int quadrant = 0;
int boundary = len / 2 - 1;
if (boundary >= row && boundary >= col) {
quadrant = 1;
}
else if (boundary >= row && boundary < col) {
quadrant = 2;
}
else if (boundary < row && boundary >= col) {
quadrant = 3;
}
else if (boundary < row && boundary < col) {
quadrant = 4;
}
int[] array = compaction.get(quadrant);
int num = blocks.get(block);
if (array == null) { // 해당 사분면에 대한 값이 저장되어 있지 않을 때
if (num == 0) {
compaction.put(quadrant, new int[]{dividend, 1, 0});
}
else {
compaction.put(quadrant, new int[]{dividend, 0, 1});
}
for (int i = row - dividend + 1; i <= row; i++) {
for (int j = col - dividend + 1; j <= col; j++) {
bool[i][j] = true;
}
}
}
else {
if (array[0] == dividend) {
if (num == 0) {
compaction.put(quadrant, new int[]{dividend, array[1] + 1, array[2]});
}
else {
compaction.put(quadrant, new int[]{dividend, array[1], array[2] + 1});
}
for (int i = row - dividend + 1; i <= row; i++) {
for (int j = col - dividend + 1; j <= col; j++) {
bool[i][j] = true;
}
}
}
}
}
}
}
}
dividend /= 2;
}
int[] result = {0, 0};
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
if (bool[i][j] == true) {
continue;
}
else {
if (arr[i][j] == 0) {
result[0]++;
}
else {
result[1]++;
}
}
}
}
for (int key : compaction.keySet()) {
int[] n = compaction.get(key);
result[0] += n[1];
result[1] += n[2];
}
return result;
}
}2차 실행 오류
6.3/100
모든 원소가 0이나 1일 때를 고려하지 않았음
import java.util.Map;
import java.util.HashMap;
class Solution {
public int[] solution(int[][] arr) {
Map<Integer, Integer> blocks = new HashMap<>();
Map<Integer, Boolean> possible = new HashMap<>();
Map<Integer, int[]> compaction = new HashMap<>(); // key: 블록의 사분면, value: [영역의 크기, 0의 개수, 1의 개수]
int len = arr.length;
int dividend = len;
boolean bool[][] = new boolean[len][len];
while(true) {
if (dividend == 1) {
break;
}
int block = 0; // 현재 속한 블록의 위치
for (int row = 0; row < len; row++) {
if (row % dividend == 0) {
block = block + 1;
if (block > (len / dividend)) {
block = 1;
}
}
for (int col = 0; col < len; col++) {
if (col % dividend == 0) {
if (row % dividend == 0 && col == 0) {
blocks.clear();
blocks.put(block, arr[row][col]);
possible.put(block, true);
}
else if (row % dividend != 0) {
block = block + 1;
if (block > (len / dividend)) {
block = 1;
}
}
else {
block = block + 1;
if (block > (len / dividend)) {
block = 1;
}
blocks.put(block, arr[row][col]);
possible.put(block, true);
}
}
if (arr[row][col] != blocks.get(block)) {
possible.put(block, false);
}
if (row % dividend == dividend - 1 && col % dividend == dividend - 1) { // 한 블록이 끝났을 때
if (possible.get(block) == true) { // 압축 가능할 때
if (dividend == len) {
int n = blocks.get(block);
if (n == 0) {
return new int[] {1, 0};
}
else {
return new int[] {0, 1};
}
}
int quadrant = 0;
int boundary = len / 2 - 1;
if (boundary >= row && boundary >= col) {
quadrant = 1;
}
else if (boundary >= row && boundary < col) {
quadrant = 2;
}
else if (boundary < row && boundary >= col) {
quadrant = 3;
}
else if (boundary < row && boundary < col) {
quadrant = 4;
}
int[] array = compaction.get(quadrant);
int num = blocks.get(block);
if (array == null) { // 해당 사분면에 대한 값이 저장되어 있지 않을 때
if (num == 0) {
compaction.put(quadrant, new int[]{dividend, 1, 0});
}
else {
compaction.put(quadrant, new int[]{dividend, 0, 1});
}
for (int i = row - dividend + 1; i <= row; i++) {
for (int j = col - dividend + 1; j <= col; j++) {
bool[i][j] = true;
}
}
}
else {
if (array[0] == dividend) {
if (num == 0) {
compaction.put(quadrant, new int[]{dividend, array[1] + 1, array[2]});
}
else {
compaction.put(quadrant, new int[]{dividend, array[1], array[2] + 1});
}
for (int i = row - dividend + 1; i <= row; i++) {
for (int j = col - dividend + 1; j <= col; j++) {
bool[i][j] = true;
}
}
}
}
}
}
}
}
dividend /= 2;
}
int[] result = {0, 0};
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
if (bool[i][j] == true) {
continue;
}
else {
if (arr[i][j] == 0) {
result[0]++;
}
else {
result[1]++;
}
}
}
}
for (int key : compaction.keySet()) {
int[] n = compaction.get(key);
result[0] += n[1];
result[1] += n[2];
}
return result;
}
}나의 코드 + AI 코드
소요 시간: 4시간
시간 복잡도:
사분면을 사용해서 해결하는 방법으로 해결하고자 했으나,
예)
8x8이상의 크기를 가진 배열에서 같은 사분면에서의 dividend == 4일 때,
dividend == 2인 압축 가능한 원소가
이전에 압축된 dividend == 4의 범위에 포함이 되지 않는 경우를 고려하지 않음
이는 dividend가 꼭 4, 2가 아니어도 다른 경우에도 구조적인 오류가 발생함해당 방법으로는 구조적으로 해결이 불가능함을 AI를 통해 알게 되었음
따라서 기존의 bool 배열을 이용하여
이전의 더 큰 dividend를 가지는 압축된 범위가
현재 더 작은 dividend에 포함이 되는지 여부를 통해 판별함
import java.util.Map;
import java.util.HashMap;
class Solution {
public int[] solution(int[][] arr) {
int[] result = {0, 0};
Map<Integer, Integer> blocks = new HashMap<>();
Map<Integer, Boolean> possible = new HashMap<>();
Map<Integer, int[]> compaction = new HashMap<>(); // key: 블록의 사분면, value: [영역의 크기, 0의 개수, 1의 개수]
int len = arr.length;
int dividend = len;
boolean bool[][] = new boolean[len][len];
while(true) {
if (dividend == 1) {
break;
}
int block = 0; // 현재 속한 블록의 위치
for (int row = 0; row < len; row++) {
if (row % dividend == 0) {
block = block + 1;
if (block > (len / dividend)) {
block = 1;
}
}
for (int col = 0; col < len; col++) {
if (col % dividend == 0) {
if (row % dividend == 0 && col == 0) {
blocks.clear();
blocks.put(block, arr[row][col]);
possible.put(block, true);
}
else if (row % dividend != 0) {
block = block + 1;
if (block > (len / dividend)) {
block = 1;
}
}
else {
block = block + 1;
if (block > (len / dividend)) {
block = 1;
}
blocks.put(block, arr[row][col]);
possible.put(block, true);
}
}
if (arr[row][col] != blocks.get(block)) {
possible.put(block, false);
}
if (row % dividend == dividend - 1 && col % dividend == dividend - 1) { // 한 블록이 끝났을 때
if (possible.get(block) == true) { // 압축 가능할 때
int topRow = row - dividend + 1;
int topCol = col - dividend + 1;
if (!bool[topRow][topCol]) { // 아직 압축이 되지 않은 영역일 때
int num = blocks.get(block);
if (num == 0) {
result[0]++;
}
else {
result[1]++;
}
for (int i = topRow; i <= row; i++) {
for (int j = topCol; j <= col; j++) {
bool[i][j] = true;
}
}
}
}
}
}
}
dividend /= 2;
}
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
if (!bool[i][j]) {
if (arr[i][j] == 0) {
result[0]++;
}
else {
result[1]++;
}
}
}
}
return result;
}
}AI 코드
시간 복잡도:
해당 코드를 보고 재귀 함수의 활용을 너무 못하고 있구나 하는 동시에
이와 같은 코드를 짜는 것이 너무 어려운 것 같다는 생각이 들었음
따라서 앞으로 문제를 해결하는 과정에 있어서
"같은 규칙이 크기만 다르게 반복"되는 경우 재귀를 고려해봐야겠다는 생각을 함
class Solution {
int[] result;
public int[] solution(int[][] arr) {
result = new int[2];
compress(arr, 0, 0, arr.length);
return result;
}
private void compress(int[][] arr, int r, int c, int size) {
int first = arr[r][c];
for (int i = r; i < r + size; i++) {
for (int j = c; j < c + size; j++) {
if (arr[i][j] != first) {
int half = size / 2;
compress(arr, r, c, half);
compress(arr, r, c + half, half);
compress(arr, r + half, c, half);
compress(arr, r + half, c + half, half);
return;
}
}
}
result[first]++;
}
}