공부하고 기록하는, 경제학과 출신 개발자의 노트

프로그래밍/코딩테스트 문제풀이

[Python] 프로그래머스. 쿼드압축 후 개수세기

inspirit941 2020. 10. 14. 10:08
반응형

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

분할정복 문제.

 

백준 2630번 "색종이 만들기"와 정확히 똑같은 문제. 리턴 형식까지도 동일하다.

www.acmicpc.net/problem/2630

 

2630번: 색종이 만들기

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.

www.acmicpc.net

 

def solution(arr):
def check(y, x, n):
# 타일 1개에 도달한 경우
# 타일 값이 0이면 [1,0], 값이 1이면 [0,1]을 리턴한다.
if n == 1:
return [0, 1] if arr[y][x] == 1 else [1,0]
# 전체 사각형의 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 확인한다.
left_up = check(y, x, n // 2)
right_up = check(y, x + n//2, n//2)
left_down = check(y+n//2, x, n//2)
right_down = check(y + n//2, x + n//2, n//2)
# 사분면 네 개가 전부 동일한 값일 경우 = 네 개가 아니라 한 개로 취급한다.
if left_up == right_up == left_down == right_down == [0,1] or left_up == right_up == left_down == right_down == [1,0]:
return left_up
else:
# 사분면 네 개의 리스트 값을 idx별로 합한 결과를 리턴한다.
return list(map(sum, zip(left_up, right_up, right_down, left_down)))
result = check(0,0,len(arr))
return result
반응형