또 다시 돌아온 백준 문제 풀이네요!
저는 보통 solved.ac 사이트에서 랭크별로 문제를 푸는데,
실버 4번에서 흥미 돋는 제목이 있어 풀어봤어요!
문제를 풀다가 느낀 저만의 포인트를 가지고 간단한 개념도 짚고 넘어갈거에요!
-문제
https://www.acmicpc.net/problem/1051
1051번: 숫자 정사각형
N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행
www.acmicpc.net
이번 문제도 마찬가지로 두 개의 풀이 방법을 생각해보았어요.
채점 기준에서 이상은 없었지만 혼자 문제를 풀이하는 동안 조금 더 효율적인 프로그램을 만들 방법을 생각하다가 채점 현황을 문득보니 제 코드의 속도가 너무 느리더라고요ㅠㅠ
그래서 이를 조금이라도 개선할 수 있는 방안을 생각해보았어요.
먼저 소스코드 보시죠!
-소스코드(개선 전)
def squ(w, x, y, z):
distinct = [w, x, y, z]
distinct.sort()
if distinct[0] == distinct[3]:
return 1
else:
return 0
N, M = map(int, input().split())
num= []
for i in range(1, N + 1):
a = list(input())
num.append(a)
if N > M :
sm = M
big = N
else:
sm = N
big = M
ans = []
for j in range(1, sm + 1): #repeat by the scale of square
for n in range(1, N - (sm - j) + 1): #investigate lateral direction
for m in range(1, M - (sm - j) + 1): #investigate vertical direction
w = num[n-1][m-1]
x = num[n-1+(sm-j)][m-1]
y = num[n-1][m-1+(sm-j)]
z = num[n-1+(sm-j)][m-1+(sm-j)]
if squ(w, x, y, z) == 1:
ans.append(sm-j +1)
print(max(ans)**2)-소스코드(개선 후)
def squ(w, x, y, z):
distinct = [w, x, y, z]
distinct.sort()
if distinct[0] == distinct[3]:
return 1
else:
return 0
N, M = map(int, input().split())
num= []
for i in range(1, N + 1):
a = list(input())
num.append(a)
if N > M :
sm = M
big = N
else:
sm = N
big = M
def whole(sm, N, num):
for j in range(1, sm + 1): #repeat by the scale of square
for n in range(1, N - (sm - j) + 1): #investigate lateral direction
for m in range(1, M - (sm - j) + 1): #investigate vertical direction
w = num[n-1][m-1]
x = num[n-1+(sm-j)][m-1]
y = num[n-1][m-1+(sm-j)]
z = num[n-1+(sm-j)][m-1+(sm-j)]
if squ(w, x, y, z) == 1:
return sm-j +1
print(whole(sm, N , num)**2)
소스코드 자체는 개선 전이나 개선 후 대동소이하다는 걸 볼 수 있을거에요.
아마 동일한 논리로 문제를 풀어나갔기 때문이겠죠? 하지만 그래도 아래 사진처럼 속도는 개선 후가 조금 더 빨라졌다는 점!
(물론 다른 잘 짠 코드보다는 현저히 느린 속도를 자랑하는 나..ㅠㅠㅠ)
아무튼 제 풀이를 설명하며 어느 부분에서 속도 차이가 난건지 알아볼게요!
-풀이
먼저 '숫자 정사각형' 문제를 이해하면서 두 가지 생각을 했어요.
답을 얻는 과정이 이렇게 될 수 있겠구나.
1번 : 체스판처럼 왼쪽 위의 숫자부터 그 숫자를 포함하여 정사각형이 될 수 있는 경우를 조사한다!
2번 : 가장 큰 정사각형부터 가장 작은 정사각형까지 내림차순으로 조사한다!
1번 방법의 경우에는 리스트를 이용하는 과정에서 부주의한 저의 실수로 인덱스 에러가 왕창 날게 훤하기도 하고, 가장 큰 정사각형의 크기를 구하는 문제의 취지에도 2번이 적합할 거 같아서 2번 방법으로 문제를 파고들었어요!
먼저 입력받은 숫자들을 이중 리스트에 편입시켰고, 정사각형의 네 점을 입력하면 네 점이 동일한지 판단하는 squ 함수도 선언해줬어요.
그리고 가장 큰 정사각형의 한 변의 길이는 N과 M 중 작은 수보다 클 수 없기에 이를 통해 조사할 경우를 한정합니다!
그러고는 정사각형의 크기를 줄여가며 조사하는 반복문 안에 가로방향, 세로방향으로 정사각형이 가능한 경우의 수를 조사할 수 있게 3중 반복문을 썼어요.
개선 전의 소스코드의 경우에는 조사 결과를 다 새로운 리스트에 때려넣어, 그중 가장 큰 값을 뽑아내는 방향으로 문제를 풀었어요.
하지만, 제가 2번 방법을 선택한 이유를 생각해보면, 조건을 만족하는 가장 큰 정사각형을 찾은 순간에 문제 풀이를 그만들 수 있을 떄 프로그램의 효율이 가장 좋아요.
그래서 '개선 후'라는 소스코드 방법을 생각한 거에요.
-중첩 반복문 탈출하기(ft. return)
개선 후 코드를 작성할 때 처음에는 생각없이 break를 붙였어요. 그러니까 반복문을 하나밖에 탈출하지 못하더라고요...
그래서 모든 반복문을 탈출시킬 방법, 혹은 프로그램을 중단시킬 방법을 생각했죠. 그것은 바로 return!
함수를 선언할 때, 내놓을 값을 return을 통해서 전달하죠.
이를 다시 생각해보면 return은 함수의 가능을 종료하는 명령이라 볼 수 있어요.
따라서 3중 반복문을 빠져나가려고 break를 배치하는데 노력하기 보다는 이용하려고 하는 삼중 반복문을 하나의 함수로 선언해서 값을 얻었을 때 return해버린다!라고 생각하면 됩니당
하지만 코린이인 저는 또 다시 당황했어요...
함수에 매개변수로 list타입을 넣어도 되나..?
-함수는 리스트타입을 매개변수(parameter)로 쓸 수 있는가?
소스코드만 봐도 알겠지만 답은 당연히 'yes'에요.
함수의 경우에는 인자(argument)를 받아들일 때, 해당 인자의 주소로 가서 인자를 스캔하기 때문에 리스트형을 이용해 함수를 선언하는 것도 문제가 없답니다!
사실 제가 문제 풀 때 리스트를 파라미터로 설정해서 에러가 뜬 적이 몇번 있었는데 이번엔 에러 안나서 다음에 에러가 나면 다시 그거에 관해서 포스팅하도록 하겠습니다~!
그리고 리스트 형은 iterable해서 선언한 함수 내에서 append같은 메서드를 쓰면 무슨 일이 일어난다고도 하는데 그것도 기회 되면 나중에 다루겠습니당!
에라 모르겠다~!
'백준 문제 풀이 Python' 카테고리의 다른 글
| [백준/파이썬] 5014번: 스타트링크 (BFS a.k.a 너비우선탐색) (0) | 2022.11.25 |
|---|---|
| [백준/파이썬] 1182번: 부분수열의 합 (0) | 2022.11.24 |
| [백준/파이썬] 1406번: 에디터 (0) | 2022.11.23 |
| [백준/파이썬] 2644번: 촌수계산 (0) | 2022.11.22 |
| [백준/파이썬] 11653번(소인수분해 풀이) (0) | 2022.07.23 |