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

'하루에 한 문제는 풀자'로 인해 프로그래머스에서 level 1은 다 풀었고 level 2는 한 페이지 정도 남았다! 약 20문제! 이제 level 3랑 병행해가면서 풀어야겠다😘

 

코딩테스트 연습 - 쿼드압축 후 개수 세기

문제 설명

이번 문제는 그림하고 입출력 예만 보면 이해할 수 있는 문제이다.

해당 그림만 보면 알겠지만 입력된 문자열을 오른쪽 상단 왼쪽 상단 오른쪽 하단 왼쪽 하단으로 나눠서 숫자가 모두 같다면 압축을 진행하고 아니면 다시 4등분으로 나눠서 압축을 진행하는 식의 문제이다.

리턴 값은 아래의 입출력 예과 같이 최종으로 압축된 내용에서 0의 개수와 1의 개수를 세어 각각의 자리에 리턴하는 문제이다.

arr	result
[[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]]	[4,9]

 

중요한 제한사항으로는 문제는 2의 제곱만으로 배열이 정의되어있다.

 

풀이 방법

재귀로 각각의 구역에 맞게 함수를 돌리고 압축이 가능하면 함수를 끝내는 식으로 하여 맨 오른쪽 그림처럼 끝까지 갈 때까지 진행한다.

 

왜?

보통 이런 문제는 일일이 돌아가면서 처리를 할 경우 시간 초과가 나거나 논리적 오류가 날 가능성이 높다.

그래서 기준을 정해 놓고 돌리는 게 가장 빠르고 정확하다고 생각하여 해당 방법으로 정했다.  

 

코드

global zero#개수를 세기위해서 global로 선언
zero=0
global one#개수를 세기위해서 global로 선언
one=0
def solution(arr):
    global zero
    global one
    answer = []
    compression(arr,0,len(arr),0,len(arr))#재귀로간다.
    answer.append(zero)
    answer.append(one)
    return answer

def compression(arr,afirst,alast,bfirst,blast):
    global zero
    global one
    word=arr[afirst][bfirst]#들어온 첫번째값을 기준으로 잡고 

    standard=True
    for i in range(afirst,alast):#그 부분들을 다 돌려돌려 돌림판
        for j in range(bfirst,blast):
            if arr[i][j]!=word:#만약 첫번째값이랑 다른게 나오면 바로 break
                standard=False
                break
        if standard==False:#위에 break문을 적용시키기위해 standard 변수와 함께 써서 break문 처리
            break
    else:#만약 첫번째값과 모든 값이 다 같다면 값에 따라 0,1인지 넣기
        if word==0:
            zero+=1
        else:
            one+=1
        return 0 #모든 값은 언젠가 여기 구문에 들어올테니 return 0

    #재귀로 오른쪽 상단하단 왼쪽 상단하단 다 돌기.
    compression(arr,afirst,alast-int((alast-afirst)/2),bfirst,blast-int((blast-bfirst)/2))#왼쪽 상단
    compression(arr,afirst+int((alast-afirst)/2),alast,bfirst,blast-int((blast-bfirst)/2))#오른쪽 상단
    compression(arr,afirst,alast-int((alast-afirst)/2),bfirst+int((blast-bfirst)/2),blast)#왼쪽 하단
    compression(arr,afirst+int((alast-afirst)/2),alast,bfirst+int((blast-bfirst)/2),blast)#오른쪽 하단
    return 0

 

실행 결과