algo lev-2 카펫 (python)

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 빨간색으로 칠해져 있고 모서리는 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 빨간색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 빨간색 격자의 수 red가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

(제한 : 가로는 세로보다 같거나 길다)

출처 : 프로그래머스 Level2

내가 푼 풀이

첫 번째 방법

1) red 블록의 약수를 구하고

2) 1번의 약수 조합(가로,세로)이 2 * (가로+세로) + 4 == brown 이라면

​ –> 해당 약수 조합을 한겹 둘러싸는 블록의 개수가 주어진 brown의 값과 같다면

3) 약수 조합의 [red가로]+2, red세로+2] 결과를 출력

• 시간초과.py (실패)

  def solution(brown, red):
      red1 = red//2 +1    
      for i in range(1,red1+1) :
          for j in range(1,red1+1):
              if i*j == red :
                  if 2*(i+j)+4 == brown :
                      return [max(i,j)+2, min(i,j)+2]
      return 
  

  • 약수를 구하는데 시간이 너무 많이 걸려서 시간초과로 실패했다

• 성공.py

  def solution(brown, red):
      for i in range(1,red//2+2) :
          for j in reversed(range(red//i+1)) :
              if i*j == red :
                  if 2*(i+j)+4 == brown :
                      return [max(i,j)+2, min(i,j)+2]
                  break
      return
  

  • 위의 풀이와 비슷하지만 최대한 for 루프를 적게 돌 수 있게 처리하고 원하는 값을 찾으면 break로 루프를 바로 종료했다
  • 하지만 여전히 시간이 너무 오래 걸렸고, 다른 방법으로 접근할 수 있는 지를 고민했다

두 번째 방법

​ 1) red를 나누어떨어지게 하는 i 값이 있고

​ 2) 2*(i, red//i)+4 == brown 해당 조건을 만족한다면

​ 3) [red//i+2, i+2] 반환

• 굳이 어렵게 약수의 조합을 구할 필요가 없었다!!

  def solution(brown, red):
      for i in range(1, red//2+1):
          if red % i == 0:
              if 2*(i + red//i)+4 == brown:
                  return [red//i+2, i+2]
  

배운점

• 다양한 방법으로 문제 풀어보기 (이중 for문 짱시름!)