๐ป
[ํ๋ก๊ทธ๋๋จธ์ค] ์๊ฐ ์ฝ๋ ์ฑ๋ฆฐ์ง - ์ฟผ๋์์ถ ํ ๊ฐ์ ์ธ๊ธฐ ๋ณธ๋ฌธ
์๊ณ ๋ฆฌ์ฆ/๋ฌธ์ ํ์ด Programmers
[ํ๋ก๊ทธ๋๋จธ์ค] ์๊ฐ ์ฝ๋ ์ฑ๋ฆฐ์ง - ์ฟผ๋์์ถ ํ ๊ฐ์ ์ธ๊ธฐ
๋ํจ๋ 2020. 10. 21. 15:25programmers.co.kr/learn/courses/30/lessons/68936
๋ฌธ์ ์ค๋ช
0๊ณผ 1๋ก ์ด๋ฃจ์ด์ง 2n x 2n ํฌ๊ธฐ์ 2์ฐจ์ ์ ์ ๋ฐฐ์ด arr์ด ์์ต๋๋ค. ๋น์ ์ ์ด arr์ ์ฟผ๋ ํธ๋ฆฌ์ ๊ฐ์ ๋ฐฉ์์ผ๋ก ์์ถํ๊ณ ์ ํฉ๋๋ค. ๊ตฌ์ฒด์ ์ธ ๋ฐฉ์์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
- ๋น์ ์ด ์์ถํ๊ณ ์ ํ๋ ํน์ ์์ญ์ S๋ผ๊ณ ์ ์ํฉ๋๋ค.
- ๋ง์ฝ S ๋ด๋ถ์ ์๋ ๋ชจ๋ ์๊ฐ ๊ฐ์ ๊ฐ์ด๋ผ๋ฉด, S๋ฅผ ํด๋น ์ ํ๋๋ก ์์ถ์ํต๋๋ค.
- ๊ทธ๋ ์ง ์๋ค๋ฉด, S๋ฅผ ์ ํํ 4๊ฐ์ ๊ท ์ผํ ์ ์ฌ๊ฐํ ์์ญ(์ ์ถ๋ ฅ ์๋ฅผ ์ฐธ๊ณ ํด์ฃผ์๊ธฐ ๋ฐ๋๋๋ค.)์ผ๋ก ์ชผ๊ฐ ๋ค, ๊ฐ ์ ์ฌ๊ฐํ ์์ญ์ ๋ํด ๊ฐ์ ๋ฐฉ์์ ์์ถ์ ์๋ํฉ๋๋ค.
arr์ด ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง๋๋ค. ์์ ๊ฐ์ ๋ฐฉ์์ผ๋ก arr์ ์์ถํ์ ๋, ๋ฐฐ์ด์ ์ต์ข ์ ์ผ๋ก ๋จ๋ 0์ ๊ฐ์์ 1์ ๊ฐ์๋ฅผ ๋ฐฐ์ด์ ๋ด์์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
์ ํ์ฌํญ
- arr์ ํ์ ๊ฐ์๋ 1 ์ด์ 1024 ์ดํ์ด๋ฉฐ, 2์ ๊ฑฐ๋ญ ์ ๊ณฑ์ ํํ๋ฅผ ํ๊ณ ์์ต๋๋ค. ์ฆ, arr์ ํ์ ๊ฐ์๋ 1, 2, 4, 8, ..., 1024 ์ค ํ๋์
๋๋ค.
- arr์ ๊ฐ ํ์ ๊ธธ์ด๋ arr์ ํ์ ๊ฐ์์ ๊ฐ์ต๋๋ค. ์ฆ, arr์ ์ ์ฌ๊ฐํ ๋ฐฐ์ด์ ๋๋ค.
- arr์ ๊ฐ ํ์ ์๋ ๋ชจ๋ ๊ฐ์ 0 ๋๋ 1 ์ ๋๋ค.
์ ์ถ๋ ฅ ์
arrresult
[[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
- ๋ค์ ๊ทธ๋ฆผ์ ์ฃผ์ด์ง arr์ ์์ถํ๋ ๊ณผ์ ์ ๋ํ๋ธ ๊ฒ์ ๋๋ค.
- ์ต์ข ์์ถ ๊ฒฐ๊ณผ์ 0์ด 4๊ฐ, 1์ด 9๊ฐ ์์ผ๋ฏ๋ก, [4,9]๋ฅผ return ํด์ผ ํฉ๋๋ค.
์ ์ถ๋ ฅ ์ #2
- ๋ค์ ๊ทธ๋ฆผ์ ์ฃผ์ด์ง arr์ ์์ถํ๋ ๊ณผ์ ์ ๋ํ๋ธ ๊ฒ์ ๋๋ค.
- ์ต์ข ์์ถ ๊ฒฐ๊ณผ์ 0์ด 10๊ฐ, 1์ด 15๊ฐ ์์ผ๋ฏ๋ก, [10,15]๋ฅผ return ํด์ผ ํฉ๋๋ค.
ํ์ด๋ฐฉ๋ฒ
์ฌ๊ทํธ์ถ๊ณผ ์์ ํ์ ์๊ณ ๋ฆฌ์ฆ์ ์ด์ฉํด์ ํ์๋ค.
1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include <string>
#include <vector>
using namespace std;
int one = 0, zero = 0;
int map[1025][1025];
void compress(int x1, int x2, int y1, int y2){
int count = 0;
for(int i=x1; i<x2; i++){
for(int j=y1; j<y2; j++){
if(map[i][j] == 1){
count ++;
}
}
}
if((x2-x1)*(y2-y1) == count) one++;
else if(count == 0) zero ++;
else{
int a = (x1 + x2)/2;
int b = (y1 + y2)/2;
compress(x1, a, y1, b);
compress(x1, a, b, y2);
compress(a, x2, y1, b);
compress(a, x2, b, y2);
}
}
vector<int> solution(vector<vector<int>> arr) {
vector<int> answer;
int n = arr.size();
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
map[i][j] = arr[i][j];
}
}
compress(0, n, 0, n);
answer.push_back(zero);
answer.push_back(one);
return answer;
}
|
cs |
2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include <string>
#include <vector>
using namespace std;
vector<vector<int>> map;
void compress(int x, int y, int size, vector<int> &answer){
if(size == 1){
if(map[x][y]==0) {
answer[0]++;
return;
}
else {
answer[1]++;
return;
}
}
bool one = true, zero = true;
for(int i=x; i<x+size; i++){
for(int j=y; j<y+size; j++){
if(map[i][j]==0) one = false;
if(map[i][j]==1) zero = false;
}
}
if(zero){
answer[0]++;
return;
}
if(one){
answer[1]++;
return;
}
compress(x, y, size/2, answer);
compress(x, y+size/2, size/2, answer);
compress(x+size/2, y, size/2, answer);
compress(x+size/2, y+size/2, size/2, answer);
}
vector<int> solution(vector<vector<int>> arr) {
vector<int> answer(2, 0); //์ฌ์ด์ฆ๊ฐ 2์ธ ๋ฒกํฐ 0์ผ๋ก ์ด๊ธฐํ
map = arr;
int n = arr.size();
compress(0, 0, n, answer);
return answer;
}
|
cs |
๋ฐ์ํ
'์๊ณ ๋ฆฌ์ฆ > ๋ฌธ์ ํ์ด Programmers' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[ํ๋ก๊ทธ๋๋จธ์ค] [1์ฐจ] ๋คํธ ๊ฒ์ (0) | 2020.05.07 |
---|---|
[ํ๋ก๊ทธ๋๋จธ์ค][2019 KAKAO ๋ธ๋ผ์ธ๋ ์ฑ์ฉ] ์คํจ์จ (0) | 2020.04.11 |
[ํ๋ก๊ทธ๋๋จธ์ค][2020 KAKAO ๋ธ๋ผ์ธ๋ ์ฑ์ฉ] ๊ดํธ๋ณํ (0) | 2020.04.11 |
[ํ๋ก๊ทธ๋๋จธ์ค] ์์ฅ (0) | 2020.04.11 |
Comments