[Programmers][Level2][Python]가장큰정사각형찾기
문제
풀이
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으로 초기화한 배열을 생성할 수 있다.
배열에 가장 작은 정사각형은 원소 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 사용이 불가피한데 데이터 개수가 증가할 때 효율성에 문제가 없을지 공부가 필요하다.
Author And Source
이 문제에 관하여([Programmers][Level2][Python]가장큰정사각형찾기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bae12/ProgrammersLevel2Python가장큰정사각형찾기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)