๐Ÿ’ป

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ์›”๊ฐ„ ์ฝ”๋“œ ์ฑŒ๋ฆฐ์ง€ - ์ฟผ๋“œ์••์ถ• ํ›„ ๊ฐœ์ˆ˜ ์„ธ๊ธฐ ๋ณธ๋ฌธ

์•Œ๊ณ ๋ฆฌ์ฆ˜/๋ฌธ์ œํ’€์ด Programmers

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ์›”๊ฐ„ ์ฝ”๋“œ ์ฑŒ๋ฆฐ์ง€ - ์ฟผ๋“œ์••์ถ• ํ›„ ๊ฐœ์ˆ˜ ์„ธ๊ธฐ

๋˜ํšจ๋‹ˆ 2020. 10. 21. 15:25

programmers.co.kr/learn/courses/30/lessons/68936

 

์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ์ฟผ๋“œ์••์ถ• ํ›„ ๊ฐœ์ˆ˜ ์„ธ๊ธฐ

[[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]

programmers.co.kr

 

๋ฌธ์ œ ์„ค๋ช…

0๊ณผ 1๋กœ ์ด๋ฃจ์–ด์ง„ 2n x 2n ํฌ๊ธฐ์˜ 2์ฐจ์› ์ •์ˆ˜ ๋ฐฐ์—ด arr์ด ์žˆ์Šต๋‹ˆ๋‹ค. ๋‹น์‹ ์€ ์ด arr์„ ์ฟผ๋“œ ํŠธ๋ฆฌ์™€ ๊ฐ™์€ ๋ฐฉ์‹์œผ๋กœ ์••์ถ•ํ•˜๊ณ ์ž ํ•ฉ๋‹ˆ๋‹ค. ๊ตฌ์ฒด์ ์ธ ๋ฐฉ์‹์€ ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.

  1. ๋‹น์‹ ์ด ์••์ถ•ํ•˜๊ณ ์ž ํ•˜๋Š” ํŠน์ • ์˜์—ญ์„ S๋ผ๊ณ  ์ •์˜ํ•ฉ๋‹ˆ๋‹ค.
  2. ๋งŒ์•ฝ S ๋‚ด๋ถ€์— ์žˆ๋Š” ๋ชจ๋“  ์ˆ˜๊ฐ€ ๊ฐ™์€ ๊ฐ’์ด๋ผ๋ฉด, S๋ฅผ ํ•ด๋‹น ์ˆ˜ ํ•˜๋‚˜๋กœ ์••์ถ•์‹œํ‚ต๋‹ˆ๋‹ค.
  3. ๊ทธ๋ ‡์ง€ ์•Š๋‹ค๋ฉด, 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 sizevector<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/2size/2, answer);
    compress(x+size/2, y, size/2, answer);
    compress(x+size/2, y+size/2size/2, answer);
    
}
vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer(20); //์‚ฌ์ด์ฆˆ๊ฐ€ 2์ธ ๋ฒกํ„ฐ 0์œผ๋กœ ์ดˆ๊ธฐํ™”
    map = arr;
    int n = arr.size();
    compress(00, n, answer);
    return answer;
}
cs
๋ฐ˜์‘ํ˜•
Comments