하루에 한 문제
[프로그래머스 월간 코드 챌린지 시즌1] 쿼드압축 후 개수 세기 -Java 본문
https://programmers.co.kr/learn/courses/30/lessons/68936
class Solution {
public int[] solution(int[][] arr) {
int[] answer = new int[2];
solve(answer, arr,0,0,arr.length, arr.length,arr.length);
return answer;
}
public void solve(int []answer, int [][]arr,int sx,int sy,int ex,int ey, int n){
int num=arr[sx][sy];
int cnt=0;
for(int i=sx; i<ex; i++){
for(int j=sy; j<ey; j++){
if(arr[i][j]!=num){ //다르다면 놔눠서 다시 부르기
solve(answer, arr, sx,sy,sx+n/2, sy+n/2, n/2);
solve(answer, arr, sx,sy+n/2,sx+n/2, sy+n, n/2);
solve(answer, arr, sx+n/2,sy,sx+n, sy+n/2, n/2);
solve(answer, arr, sx+n/2,sy+n/2,sx+n, sy+n, n/2);
return ;
}
else cnt++;
}
}
if(cnt==n*n) answer[num]++;
}
}
소요시간 : 25분
대표적인 분할정복 문제입니다.
로직을 살펴보면
1. 현재의 사각형의 요소가 모두 같은지 확인한다.
2. 만약 모두 같다면 해당하는 요소의 배열 인덱스를 ++해준다.
3. 만약 하나라도 다른게 있다면 현재 배열을 4등분해서 1번으로 돌아간다.
재귀를 통해서 이런식으로 다른 요소가 있다면 배열의 인덱스를 고쳐서 다시 1번로직부터 실행하면 됩니다.
끝~
'알고리즘 > 프로그래머스' 카테고리의 다른 글
프로그래머스 월간 코드 챌린지 시즌 2 후기 (2) | 2021.04.15 |
---|---|
[프로그래머스 2017 카카오코드 본선] 단체사진 찍기 -Java (0) | 2021.04.13 |
[프로그래머스 2020 KAKAO BLIND RECRUITMENT] 가사 검색 -Java (0) | 2021.04.10 |
[프로그래머스 2018 KAKAO BLIND RECRUITMENT] 추석 트래픽 -Java (0) | 2021.04.09 |
[프로그래머스 2019 KAKAO BLIND RECRUITMENT] 길 찾기 게임 -Java (0) | 2021.04.08 |
Comments