๐ ํ๋ก๊ทธ๋๋จธ์ค / ์๊ฐ ์ฝ๋ ์ฑ๋ฆฐ์ง ์์ฆ 1 / Level 2 / ์ฟผ๋์์ถ ํ ๊ฐ์ ์ธ๊ธฐ
๐ ๋ฌธ์
ํ๋ก๊ทธ๋๋จธ์ค
์ฝ๋ ์ค์ฌ์ ๊ฐ๋ฐ์ ์ฑ์ฉ. ์คํ ๊ธฐ๋ฐ์ ํฌ์ง์ ๋งค์นญ. ํ๋ก๊ทธ๋๋จธ์ค์ ๊ฐ๋ฐ์ ๋ง์ถคํ ํ๋กํ์ ๋ฑ๋กํ๊ณ , ๋์ ๊ธฐ์ ๊ถํฉ์ด ์ ๋ง๋ ๊ธฐ์ ๋ค์ ๋งค์นญ ๋ฐ์ผ์ธ์.
programmers.co.kr
๐ซ ์ ํ ์ฌํญ
- arr์ ํ์ ๊ฐ์๋ 1 ์ด์ 1024 ์ดํ์ด๋ฉฐ, 2์ ๊ฑฐ๋ญ ์ ๊ณฑ์ ํํ๋ฅผ ํ๊ณ ์์ต๋๋ค. ์ฆ, arr์ ํ์ ๊ฐ์๋ 1, 2, 4, 8, ..., 1024 ์ค ํ๋์
๋๋ค.
- arr์ ๊ฐ ํ์ ๊ธธ์ด๋ arr์ ํ์ ๊ฐ์์ ๊ฐ์ต๋๋ค. ์ฆ, arr์ ์ ์ฌ๊ฐํ ๋ฐฐ์ด์ ๋๋ค.
- arr์ ๊ฐ ํ์ ์๋ ๋ชจ๋ ๊ฐ์ 0 ๋๋ 1 ์ ๋๋ค.
๐ ์ ์ถ๋ ฅ ์
| arr | result |
| [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] | [4,9] |
| [[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1], [0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1], [0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1], [0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] |
[10,15] |
๐ค ํ์ด ๋ฐฉ๋ฒ
1๏ธโฃ ๊ธฐ๋ณธ ์์ด๋์ด
โก๏ธ ์ต๋ ํฌ๊ธฐ (= ๋ฐฐ์ด์ ํฌ๊ธฐ) ๋ถํฐ ์์ํด์ 1/2 ์ฉ ์ค์ฌ๋๊ฐ๋ค. ์ค์ฌ๋๊ฐ๋ ๊ณผ์ ์์๋ ์ฌ๊ท๊ฐ ์ฐ์ธ๋ค.
2๏ธโฃ 1 ๊ณผ 0 ์ ๊ฐ์ ํ์ธ
โก๏ธ ์ ์ฒด๋ฅผ ํ์ํ๋ฉฐ one (= 1์ ๊ฐ์) ์ ํ์ธํ๋ค. ์ ์ฒด ์์์ ๊ฐ์์์ one ์ ๋นผ๋ฉด zero (= 0์ ๊ฐ์) ์ด๋ค.
3๏ธโฃ ์ค๋ช (์ ์ถ๋ ฅ ์ 2๋ฒ)
โ limit = 8

โก๏ธ ๊ธธ์ด(=l imit) ๊ฐ 8์ธ ๊ฒฝ์ฐ๋ ๊ฐ๋ฅํ ๊ฒฝ์ฐ๋ค ์ค ๊ฐ์ฅ ์ต๋ ํฌ๊ธฐ์ด๋ค. (0,0) ๋ถํฐ ํ์ธํ๋ฉฐ ๊ณ์ํด์ ๊ฐ์ ๊ฐ์ด ๋์ค๋์ง ํ์ธํ๋ค. ํ์ฌ ์ํ์์๋ (1,0) ์์ ๋ฌธ์ ๊ฐ ์๊ธฐ๋ฏ๋ก 4๊ฐ์ ๊ท ์ผํ ์ ์ฌ๊ฐํ์ผ๋ก ์ชผ๊ฐ์ ธ์ผํ๋ค.
// ์ฒซ๋ฒ์งธ ์์
int tmp = Arr[x][y];
// ํ์
for (int i=x; i<x+limit; i++) {
for (int j=y; j<y+limit; j++) {
if (tmp != Arr[i][j]) { // ๊ฒฝ์ฐ โ : ์์ถ์ ์คํจํ ๊ฒฝ์ฐ โก๏ธ ๋ถํ
// ๋ค์ ๋จ๊ณ์์ ํ์ธ
}
}
}
โก limit = 4

โก๏ธ 4๊ฐ์ ๊ท ์ผํ ์ ์ฌ๊ฐํ์ผ๋ก ๋ถํ ํ ๋ชจ์ต์ด๋ค. ๊ฐ ์์ ์ง์ ์ด ๊ทธ ๋ค์ ์ต๋ ํฌ๊ธฐ์ธ ๊ธธ์ด๊ฐ 4 (= 8/2) ๋ฅผ ๋ถ๊ธฐ๋ก ๋์ด ์ง๊ฒ ๋์ด (0,0) / (0,4) / (4,0) / (4,4) ์ด 4๊ฐ๊ฐ ๋๋ค.
// ๊ธฐ์กด ๊ธธ์ด์์ ์ ๋ฐ์ผ๋ก ์ค์
limit = limit / 2;
// 4๊ฐ์ ๋ถ๊ธฐ๋ก ๋ถํ
quad(x, y, limit);
quad(x, y + limit, limit);
quad(x + limit, y, limit);
quad(x + limit, y+limit, limit);
โข limit = 2

โก๏ธ ๋จผ์ ์ ๊ทธ๋ฆผ์์์ ๋๋ฒ์งธ, ์ธ๋ฒ์งธ ๋ถํ ๊ตฌ์ญ์ ๋ณด๋ฉด ๋ชจ๋ 1 ๋๋ 0 ์ผ๋ก ์ด๋ฃจ์ด์ก๊ธฐ ๋๋ฌธ์ ์์ถ์ด ๊ฐ๋ฅํ๋ค. ํด๋น ๊ณผ์ ์์ ๊ฐ์๋ Math.pow(limit,2) -1 ๊ฐ ๋งํผ ์ค์ด๋ ๋ค.
โก๏ธ ๋ค์ ์ฒซ๋ฒ์งธ์ ๋ค๋ฒ์งธ ๋ถํ ๊ตฌ์ญ์ ๋ณด๋ฉด ์์ ๊ฒฝ์ฐ์ ๋ง์ฐฌ๊ฐ์ง๋ก ๋ค์ํ๋ฒ ๋ถํ ๋์ด์ผํ๋ค. ๋ฐ๋ผ์ ๋ค์ ์ต๋ ํฌ๊ธฐ์ธ ๊ธธ์ด 2 ๊ฐ ๋ถ๊ธฐ๊ฐ ๋๋ค. ์ง๊ธ๋ถํฐ๋ ์ฒซ๋ฒ์งธ ๋ถํ ๊ตฌ์ญ๋ง ์ง์ค์ ์ผ๋ก ํ์ธํ๋๋ก ํ์.
// ๊ฒฝ์ฐ โก : ์์ถ์ ์ฑ๊ณตํ ๊ฒฝ์ฐ โก๏ธ ์์ถํ ๋งํผ ๊ฐ์ ์ ๊ฑฐ
if (tmp == 1) {
one = one - ((int)Math.pow(limit, 2)-1);
return;
}
zero = zero - ((int)Math.pow(limit, 2)-1);
return;
โฃ limit = 1

โก๏ธ ์์์์ ๋ถํ ๊ตฌ์ญ ์ค ๋๋ฒ์งธ, ๋ค๋ฒ์งธ ๊ตฌ์ญ์ ์์ถ ๊ฐ๋ฅํ์ฌ ๊ฐ์๊ฐ ์ค์ด๋ ๋ค.
โก๏ธ ํ์ง๋ง ์ฒซ๋ฒ์งธ, ์ธ๋ฒ์งธ ๊ตฌ์ญ์ ๋ค์ ์ชผ๊ฐ์์ผํ๋ค. ์ด๋ ๊ธธ์ด๋ 1 ์ด ๋๋๋ฐ ์ด๋ด ๊ฒฝ์ฐ ๋ ์ด์ ์ชผ๊ฐค ์ ์์ผ๋ฉฐ, ๋์์ ๊ฐ์์ ๋ณํ๋ ์์ด์ง๋ค.
// ๋ง์ง๋ง ํ ์นธ๊น์ง ์จ ๊ฒฝ์ฐ : ๋ฐ๋ก return (๊ฐ์ ๋ณํ ์์)
if (limit == 1) {
return;
}
โก๏ธ ์ ๋ด์ฉ๋ค์ ์ข ํฉํ๋ฉด ์๋์ ๊ฐ์ ์ฝ๋๋ก ์ ๋ฆฌํ ์ ์๋ค.
class Solution {
// 1 ๊ณผ 0 ์ ๊ฐ์
public static int one = 0;
public static int zero;
public static int[][] Arr;
public int[] solution(int[][] arr) {
Arr = arr;
// ํฌ๊ธฐ
int size = arr.length;
// โ ์ ์ฒด๋ฅผ ํ์ํ๋ฉฐ 1 ๊ณผ 0 ์ ๊ฐ์ ํ์
for (int i=0; i<size; i++) {
for (int j=0; j<size; j++) {
one += arr[i][j];
}
}
zero = (int) Math.pow(size,2) - one;
// โก ํ์
quad(0, 0, size);
// ๋ฐฐ์ด ์์ฑ ํ ๋ฐํ
return new int[] {zero,one};
}
public static void quad(int x, int y, int limit) {
// ์ฒซ๋ฒ์งธ ์์ ํ์ธ
int tmp = Arr[x][y];
if (limit == 1) { // ๋ง์ง๋ง ํ ์นธ๊น์ง ์จ ๊ฒฝ์ฐ : ๋ฐ๋ก return (๊ฐ์ ๋ณํ ์์)
return;
}
// ํ์
for (int i=x; i<x+limit; i++) {
for (int j=y; j<y+limit; j++) {
if (tmp != Arr[i][j]) { // ๊ฒฝ์ฐ โ : ์์ถ์ ์คํจํ ๊ฒฝ์ฐ โก๏ธ ๋ถํ
limit = limit / 2;
quad(x, y, limit);
quad(x, y + limit, limit);
quad(x + limit, y, limit);
quad(x + limit, y+limit, limit);
return;
}
}
}
// ๊ฒฝ์ฐ โก : ์์ถ์ ์ฑ๊ณตํ ๊ฒฝ์ฐ โก๏ธ ์์ถํ ๋งํผ ๊ฐ์ ์ ๊ฑฐ
if (tmp == 1) {
one = one - ((int)Math.pow(limit, 2)-1);
return;
}
zero = zero - ((int)Math.pow(limit, 2)-1);
return;
}
}
๐ป ํ์ด ์ฝ๋
[level 2] Title: ์ฟผ๋์์ถ ํ ๊ฐ์ ์ธ๊ธฐ, Time: 9.62 ms, Memory: 95.9 MB -Baekjo… · Young998904/Practice_Algorithm_Aut
…onHub
github.com