반응형
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번 "색종이 만들기"와 정확히 똑같은 문제. 리턴 형식까지도 동일하다.
2630번: 색종이 만들기
첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.
www.acmicpc.net
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
반응형
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
[Python] LeetCode 121. Best time to buy and sell stock (0) | 2020.10.21 |
---|---|
[Python] LeetCode 238. Product of Array Except self (0) | 2020.10.19 |
[Python] 프로그래머스. 3진법 뒤집기 (1) | 2020.10.12 |
[Python] LeetCode 15. 3Sum (0) | 2020.10.08 |
[Python] 프로그래머스. 줄 서는 방법 (Level 3) (0) | 2020.10.06 |