[프로그래머스] 가장 큰 정사각형 찾기

프로그래머스 1. 가장 큰 정사각형 찾기

프로그래머스 -가장 큰 정사각형 찾기

가장 큰 정사각형 찾기 문제를 실패했다..
나름대로 생각해본 로직으로 2~3시간만에 풀었는데 테스트케이스 3개가 안맞는다..

이 코드에서 배운점은 2차원 배열(2차원리스트)의 열끼리 연산하기 위해
numpy의 Transpose를 import없이 리스트로만 구현했다는 점?

방법은 zip(*iter)함수
내 코드에서는

input_list_T = list(zip(*input_list))

이렇게 구현하였는데 간단히 정리해보면 *input_list는 리스트의 요소 하나씩 접근하게 된다. 그걸 zip을 이용해서 열끼리 묶어주는 기능을 했다.
input_list가 transpose되면 이런 식으로 전개 되는데

input_list = [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]]
input_list_T = [[0,1,1,0],[1,1,1,0],[1,1,1,1],[1,1,1,0]]
#matrix의 transpose와 같은 효과!

이 input_list_T 변수는 열끼리 연산할 수 있다.
다음에도 비슷한 기능을 구현할지도 모르니 저장해두고 있어야겠다.

내 전체코드는

#연속된 n개가 있는가? 
def is_static(list_n, n):
    j = 0
    for i in list_n:
        if i >= n:
            j+=1 
            if j >= n :
                return True
        else: 
            j = 0
    return False 

def sum_static(list_n):
    j=0
    j_list=[]
    for i in list_n:
        if i > 0 :
            j += 1
        else :
            j_list.append(j)
            j= 0
    j_list.append(j)
    return max(j_list)

def solution(board):
    list_input= board
    static_cols =[]
    static_rows = []
    for i in list_input
    list_input_T = list(zip(*list_input))
    
    for i in range(len(list_input)):
        static_cols.append(sum_static(list_input[i]))
    for i in range(len(list_input_T)):
        static_rows.append(sum_static(list_input_T[i]))
    for i in range(1,1001):
        if not( (is_static(static_rows,i) == True) and (is_static(static_cols, i) == True)):
            break

    if i< 0:
        return 0
        
    return (i-1)**2

내 로직은 간단히 말해 정사각형을 만들기 위해
n=1,2,...1000까지 이 문제가 어디까지 가지고 있는지 검증하는 로직이다.

예를 들어 n==2라면 1이 연속해서 2번나온게 행에 두번 열에 두번이 연속적으로 나와야하는데 1이 연속으로 최대 몇번 나오는지는 함수 sum_static으로 판단하고 그렇게 나온값이 내가 검증하려는 n(=2)에 대해 2가 2번이상 반복되었는지를 검증하는 is_static()함수를 사용한다.

23개의 테스트중 3개를 실패했고 효율성은 다 성공했지만 어떤 테스트케이스 정답에 오류가 있다.. 점수는 90.6/100 점이다.

다른 사람들 글을 보니 DP(Dynamic Programming)문제인거 같은데
동적 계획법을 아직 안배워서 다른 사람 코드를 봐도 큰 의미는 없을 것 같다...
동적계획법을 배우면 다시 문제를 해결해 보겠다.