Question
한 변의 길이가 2의 제곱수인 정사각형의 흑백 이미지가 2차원 배열로 주어집니다. 각 좌표에는 0(백) 또는 1(흑)이 저장되어 있습니다. 이미지에 포함된 데이터가 모두 1이면 '1', 모두 0이면 '0' 한 글자로 압축할 수 있습니다. 그렇지 않은 경우, 이를 대문자 X로 표시하고 전체를 4등분하여 재귀적으로 압축합니다. 4등분한 영역의 순서는 좌측 상단, 우측 상단, 좌측 하단, 우측 하단입니다.
입력
인자 1 : image
•
배열을 요소로 갖는 배열
•
image.length, image[i].length는 1,024 이하
•
image[i]는 number 타입을 요소로 갖는 배열
•
image[i][j]는 세로로 i, 가로로 j인 지점의 정보를 의미
•
image[i][j]는 0 또는 1
출력
•
string 타입을 리턴해야 합니다.
주의사항
•
두 배열의 길이의 합은 1,000,000 이하입니다.
•
어떤 배열 arr의 k번째 요소는 arr[k-1]을 의미합니다.
Test Case 1
let image = [
[1, 0, 1, 1],
[0, 1, 1, 1],
[0, 0, 1, 1],
[0, 0, 0, 0],
];
let result = decompression(image);
console.log(result); // --> 'XX100110X1100'
Shell
복사
Test Case 2
image = [
[0, 0, 0, 0, 1, 1, 0, 0],
[0, 0, 0, 0, 1, 1, 0, 0],
[0, 0, 0, 0, 1, 1, 1, 0],
[0, 0, 0, 0, 1, 1, 1, 0],
[1, 1, 1, 1, 0, 0, 0, 0],
[1, 1, 1, 1, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 0, 1, 1],
[1, 1, 1, 1, 0, 1, 1, 1],
];
result = decompression(image);
console.log(result); // --> 'X0X101X10101X00X10011'
Shell
복사
Solve
먼저 분할해 재귀를 한다. 길이가 2일 때, 배열의 요소를 모두 문자열로 더해서 1111인지 0000인지 확인하는 방법
→ 하나씩 도는 것보다 더 효과적일듯
const decompression = function (image) {
// 재귀를 위한 보조 함수
// 파라미터는 차례대로 y좌표의 시작(Row Start), y좌표의 끝(Row End), x좌표의 시작(Col Start), x좌표의 끝(Col End)
const aux = (rs, re, cs, ce, image) => {
// base case
// 각 좌표에는 number 타입이 저장되어 있다.
if (rs === re) return String(image[rs][cs]);
// 좌상, 우상, 좌하, 우하로 구분한다.
const midRow = Math.floor((rs + re) / 2);
const midCol = Math.floor((cs + ce) / 2);
const leftUpper = aux(rs, midRow, cs, midCol, image);
const rightUpper = aux(rs, midRow, midCol + 1, ce, image);
const leftDown = aux(midRow + 1, re, cs, midCol, image);
const rightDown = aux(midRow + 1, re, midCol + 1, ce, image);
// 주어진 사각형 전체를 순회하고 나서 재귀를 하거나
// 4등분한 각 사각형을 각각 순회하고 나서 재귀를 하는 방식은 데이터를 중복 조회하게 된다.
// 재귀적으로 각 결과를 합치면서 계산하면 모든 좌표를 한 번씩만 검토하면 된다.
const result = leftUpper + rightUpper + leftDown + rightDown;
if (result === '1111') return '1';
else if (result === '0000') return '0';
else return 'X' + result;
};
return aux(0, image.length - 1, 0, image.length - 1, image);
};
JavaScript
복사
실행시간 : ms
const decompression = function (image) {
// TODO: 여기에 코드를 작성합니다.
let m = image.length;
let result = '';
const dec = (x, y, len) => {
let isSame = true;
if (len === 1) {
return '' + image[x][y];
}
for (let i = 0; i < len; i++) {
for (let j = 0; j < len; j++) {
if (image[x][y] !== image[x + i][y + j]) {
isSame = false;
break;
}
}
if (!isSame) break;
}
if (isSame) return '' + image[x][y];
len = len / 2;
let str = 'X';
str += dec(x, y, len);
str += dec(x, y + len, len);
str += dec(x + len, y, len);
str += dec(x + len, y + len, len);
return str;
}
result = dec(0, 0, m);
return result;
};
JavaScript
복사
실행시간 : ms