문제

풀이

Trial 1st 풀이

아무 생각 없이 짠 첫번째 코드이다.

배열을 돌면서 1이면 count를 1씩 추가하고 0이면 그동안 쌓인 count를 tmp 에 정렬하고 count를 0으로 초기화 후 다시 쌓는다. 이후 tmp를 돌면서 가장 긴 값을 찾는다.

def solution(board):
    answer = 0
    count = 0
    tmp = []

    for b in board:
        for i, v in enumerate(b):
            if v==1:
                count+=1
            elif count!=0 and v==0:
                tmp.append(count)
                count=0
        if count!=0:
            tmp.append(count)
            count = 0
    
    row = tmp[0]
    for i in tmp:
        if row <= i:
            count += 1
            if row == count:
                answer = count
        elif row > i:
            if row == count:
                answer = count
            row = i
            count = 0
            
    return answer*answer

일부 테스트케이스만 통과되었다. 효율성 문제가 아니라 아예 접근이 잘못 되었다.

Trial 2nd 풀이

문제를 읽을 때 가장 길이가 긴 연속된 수열 문제와 비슷하다는 생각이 들었는데 아니나 다를까 이 문제도 DP로 해결해야 하는 문제였다.

우선 주어진 배열과 같은 크기의 dp 배열을 생성하고 0으로 초기화 해준다.

# 행렬 사이즈 확인
row = len(board)
col = len(board[0])
    
# dp 배열 생성
dp = [[0]*col for _ in range(row)]

참고로 python의 반복문에서 _(언더바)를 사용하면 변수 없이 반복문을 돌릴 수 있다. nm 크기의 2차원 리스트라면 [[0]m for in range(n)] 컴프리헨션으로 0으로 초기화한 배열을 생성할 수 있다.

파이썬 반복문에서 언더바(_) 사용

[Python] 언더바 (_) 사용하기

배열에 가장 작은 정사각형은 원소 4개로 이루어진 사각형이다. arr[i][j]를 기준으로 왼쪽 위쪽 방향의 원소 arr[i-1][j-1], arr[i-1][j], arr[i][j-1] 의 값이 1이라면 사각형을 이룰 수 있는 것이다.

dp 문제에서는 부분해를 쌓아나가야 한다. 원소 4개로 이루어진 최소 크기의 정사각형이 성립하는지 아닌지 여부를 다음과 같이 저장하기로 한다.

4개의 원소 중 가장 작은 값에 1을 더한 값을 arr[i][j] 자리에 넣어준다.

이 방식을 이용하면 다음과 같이 최소 크기 정사각형의 개수가 쌓여진다.

• 정사각형이 아닐 때 arr[i][j] 값은 0 또는 1
• 처음으로 정사각형을 이루었을 때 arr[i][j] 값은 1+1 = 2
• n번 이상의 정사각형을 이루었을 때 arr[i][j] 값은 1+n

주어진 배열은 z 순서로 탐색한다. (첫번째 행을 0부터 m 까지 돌고 다음 행애에서 다시 0부터 m까지 도는 것) 다만 이때 첫번째 행과 각 행의 0번째 원소는 비교할 수 있는 대상이 없고, 다만 다음 위치의 원소가 정사각형 유무 판단을 위해 참고할 뿐이므로 고정값으로 둔다.

# 배열의 첫번째 행 채우기
dp[0] = board[0]

# 배열의 각 행 첫번째 원소 채우기
for i in range(1, row):
    dp[i][0]= board[i][0]

첫번째 행과 각 행의 첫번째 열을 제외하고 2중 for 문을 돌면서 최소 크기 정사각형 유무를 판단해 나간다. 이때 board[i][j]가 0이라면 어차피 정사각형이 될 수 없으니 1일 때만 비교를 한다. 값을 쌓아올려야 하므로 정사각형 범위 안의 최소 원소값은 dp 배열에서 구한다.

# 가장 작은 정사각형 유무를 판단하고, 결과 쌓아올리기
    for i in range(1, row):
        for j in range(1, m):
            if board[i][j] == 1:
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

이후 dp 배열에서 행별 최대값을 구하고 배열의 최대값과 비교해 값을 갱신하는 for문을 작성한다.

# 최대 넓이 구하기
    answer = 0
    for i in range(row):
        # 각 행의 최대값
        row_max = max(dp[i])
        answer = max(answer, row_max)

정사각형의 넓이를 출력하라고 했으므로 return answer**2를 해준다. 전체 코드는 다음과 같다.

def solution(board):
        
    # 행렬 사이즈 확인
    row = len(board)
    col = len(board[0])
    
    # dp 배열 생성
    dp = [[0]*col for _ in range(row)]
    
    # dp 배열 첫 번째 행 및 각 행의 첫 번째 값 채우기
    dp[0] = board[0]
    for i in range(1, row):
        dp[i][0]= board[i][0]
    
    # 가장 작은 정사각형 유무를 판단하고, 결과 쌓아올리기
    for i in range(1, row):
        for j in range(1, col):
            if board[i][j] == 1:
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
                
    # 최대 넓이 구하기
    answer = 0
    for i in range(row):
        # 각 행의 최대값
        row_max = max(dp[i])
        answer = max(answer, row_max)
    
    return answer**2

한가지 궁금한 점은, iterable을 사용해서 for 문을 돌릴 때 range 컬렉션 사용을 지양하는 것이 좋다고 알고 있다. 본 문제에서처럼 정수형 값을 돌릴 때 range 사용이 불가피한데 데이터 개수가 증가할 때 효율성에 문제가 없을지 공부가 필요하다.

[Python] for 문에서 int 형 사용하기