[Algorithm] 백준 1051

ZEDY·2024년 3월 19일

[코딩테스트] 알고리즘 문제풀이

목록 보기

16/46

문제

N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.

풀이

내가 생각한 알고리즘

i, j 순차적으로 돌면서
거기서 k만큼 떨어진 것들이 정사각형인지 확인
맞다면, 크기를 계산해 max 값을 구한다.

정답 코드

n, m = map(int, input().split(' '))

table = []

for i in range(0, n):
    num = input()
    table.append(num)

sum = 1

def check_square(i, j):
    sum = 1
    for k in range(0, min(m-j, n-i)):
        if table[i][j] == table[i+k][j] and table[i][j] == table[i][j+k] and table[i][j] == table[i+k][j+k]:
            sum = max(sum, (k+1)*(k+1))
    return sum

for i in range(0, n):
    for j in range(0, m):
        sum = max(sum, check_square(i, j))

print(sum)

개선

이 코드를 개선할 수 있는 몇 가지 방법이 있습니다:

중복 변수명 사용을 피하기:
- 코드에서 sum이라는 변수를 사용하고 있습니다. 그러나 파이썬에서는 내장 함수명으로 sum이 이미 사용되고 있습니다. 따라서 이 변수명을 다른 이름으로 변경하는 것이 좋습니다.
불필요한 계산 줄이기:
- check_square 함수 내에서 반복문을 통해 정사각형을 확인하는데, 중복되는 계산이 있습니다. 예를 들어, table[i][j] 값을 여러 번 확인하고 있습니다. 이러한 불필요한 계산을 줄이면 성능을 향상시킬 수 있습니다.
정사각형 확인 방법 개선:
- 현재 코드는 정사각형을 확인할 때 우하향 대각선 방향까지 확인하고 있습니다. 그러나 이러한 방법은 모든 경우를 고려하지 않습니다. 더 효율적인 정사각형 확인 방법을 고려하여 코드를 개선할 수 있습니다.
코드 재구성:
- 코드를 보다 간결하게 작성하고 가독성을 높일 수 있는 방법을 고려할 수 있습니다. 이를 통해 코드의 유지 보수성을 높일 수 있습니다.

이러한 방법들을 고려하여 코드를 개선할 수 있습니다.

여러 가지 개선 방법이 있지만, 여기서는 변수명을 변경하고 중복 계산을 줄이는 방법에 초점을 맞추겠습니다.

n, m = map(int, input().split(' '))

table = []

for _ in range(n):
    num = input()
    table.append(num)

max_square_size = 1  # 변수명 변경

def check_square(i, j):
    square_size = 1  # 변수명 변경
    max_possible_size = min(m - j, n - i)  # 반복 횟수 최적화
    for k in range(1, max_possible_size):  # k의 시작값 변경
        if table[i][j] == table[i + k][j] == table[i][j + k] == table[i + k][j + k]:  # 중복 계산 줄이기
            square_size = (k + 1) ** 2
    return square_size

for i in range(n):
    for j in range(m):
        max_square_size = max(max_square_size, check_square(i, j))

print(max_square_size)