알고리즘 스터디를 준비하며 풀게 된 문제이다. 물론 어려운 문제였지만 이때까지 완전 검색과 DFS를 풀면서 많이 봤던 유형이었기 때문에 어떻게 풀지 비교적 쉽게 방향을 잡을 수 있었다.
문제를 간략히 설명하자면, 배열이 주어졌을 때, 그 배열을 정사각형으로 나누고, 그 정사각형이 모두 같은 값이면 하나로 압축할 수 있고 이렇게 압축했을 때 배열의 최종적으로 남는 0의 개수와 1의 개수를 출력하는 문제이다.
이 문제에서 제공하는 그림을 본다면,
가장 왼쪽 사각형처럼 초기배열 상태에서는 모든 수가 같지 않기 때문에 2^(1/2) 배수로 정사각형을 나눠야 하고, 그렇게 나누어진 게 두 번째 사각형이다. 두 번째 사각형에서는 1 사분면의 값이 모두 같아지기 때문에 0으로 압축할 수 있다. 이 과정은 정사각형의 크기가 1이 될 때까지 반복할 수 있는데, 정사각형의 크기가 1이 된다면 더 이상 사각형의 크기를 줄일 수 없게 된다.
큰 하나의 사각형을 검사하고, 이를 네 개로 분할하여 각각 검사하고 값이 나오면 return 아니면 또 네개로 분할... 이 과정이 '나는 완전 검색 문제야!'라고 말해주는 것 같았기 때문에 우선 N의 크기를 확인해 보았는데, 1024 즉, 2^10. 분할하는 과정이 최대 10번이면 완전 검색으로 해도 시간상 넉넉할 것 같다는 생각이 바로 구현해 보았다.
코드로 나타낸다면,
def solution(arr):
def check(si, sj, ei, ej):
nonlocal answer
if si >= ei - 1 or sj >= ej - 1:
answer[arr[si][sj]] += 1
return
mid_i = (ei + si) // 2
mid_j = (sj + ej) // 2
stand = arr[si][sj]
flag = 0
for i in range(si, ei):
for j in range(sj, ej):
if stand != arr[i][j]:
flag = 1
if flag:
check(si, sj, mid_i, mid_j)
check(si, mid_j, mid_i, ej)
check(mid_i, sj, ei, mid_j)
check(mid_i, mid_j, ei, ej)
else:
answer[stand] += 1
answer = [0] * 2
si = sj = 0
ei = ej = len(arr)
check(si,sj,ei,ej)
return answer
이렇게 된다.
코드로 구현할 때, 헷갈렸던 부분이
이 부분이었다. 즉, 사각형을 검사했을 때, 사각형의 모든 값이 같지 않다면(flag==true) 사각형을 네 개로 쪼개어 재귀 함수로 들어가야 하는데 이 조건 분기가 생각보다 까다로웠다.
나는 행의 중간값과, 열의 중간 값을 미리 구하여
1. 시작행, 열은 그대로고 끝 행, 열이 중간값으로 바뀌는 함수
2. 시작행은 그대로, 끝행은 중간값으로 바뀌고 / 시작 열은 중간부터, 끝 행은 그대로인 함수
3. 시작행은 중간값, 끝행은 그대로, 시작 열은 그대로, 끝열은 중간값인 함수
4. 시작행, 열은 중간 값/ 끝행, 열은 그래도 인 함수
이렇게 네 개의 함수로 재귀를 시켰다.
그래도 익숙한 유형이라고 생각하여, 손 코딩 과정을 하지 않고 풀었는데 이런 조건 분기 부분에서 헷갈려서 시간을 많이 쓴 것 같다.
오늘도 한 번 더 손 코딩의 중요성을 느낀다.
하루 한 개 알고리즘 파이팅!
문제출처 : https://programmers.co.kr/learn/courses/30/lessons/68936
'개발' 카테고리의 다른 글
[Python] heaqp 라이브러리를 이용한 우선순위 큐 (0) | 2022.06.02 |
---|---|
[SSAFY] 1학기 최종 프로젝트 : 영화 추천 사이트 (0) | 2022.05.28 |
[Python] collections.Counter : 딕셔너리 서브 클래스 (0) | 2022.05.15 |
[Python] re 라이브러리를 이용한 정규표현식 (0) | 2022.05.07 |
[Programmers] 2021 KAKAO BLIND RECRUITMENT : 합승 택시 요금 :Python (0) | 2022.05.06 |