[programmers] Level 2 멀쩡한 사각형.py

프로그래머스 Level 2 멀쩡한 사각형을 파이썬을 통해 풀어보았다. 

 

https://programmers.co.kr/learn/courses/30/lessons/62048

코딩테스트 연습 - 멀쩡한 사각형

멀쩡한 사각형.py

tomy9729/Algorithm

Level 2 - 멀쩡한 사각형

처음에는 좌표를 통해 풀려고 했다. 전체 사각형을 가로지르는 선에 대해서 "y=(h/w)*x"꼴의 1차원 함수를 구할 수 있다. 어떤 하나의 정사각형에 대해서 정사각형의 한쪽 끝이 "y>(h/w)*x"이고 다른 대각 끝이 "y<(h/w)*x"를 만족한다면(조건) 해당 정사각형은 직선에 의해 잘리기 때문에 사용할 수 없다. 이를 통해 잘리는 정사각형을 하나씩 세면서 답을 도출했지만 시간 초과에 걸렸다. 

 

모든 사각형을 확인하는 게 시간 초과의 원인이라고 생각해서 모든 x좌표에 대해 y좌표는 (h//w)부터 위 조건을 만족하지 않는 부분까지 탐색하도록 했다. 어느 정도 빨라지긴 했지만 마찬가지로 시간 초과에 걸렸다.

 

위 과정까지 생각하고 나니 사실 "y=(h/w)*x"에 대해서 x에 대한 y값을 내림한 수의 합이 멀쩡한 사각형의 개수의 절반이다. 대각선을 기준으로 같은 모양이기 때문이다. 

 

그러므로 w와 h가 같을 때는 (w*h-w)를 바로 반환하여 시간을 더 줄일 수 있다. w나 h 중 하나라도 1일 경우에는 0을 반환한다. 

#Level 2 멀쩡한 사각형.py
def solution(w,h):
    square = 0
    #(0,0)~(w,h)
    #y = h/w x
    if w==h : 
        return w*h-w
    elif w==1 or h==1 :
        return 0
    for i in range(w) : 
        square += (int)((h*i)/w)
    return square*2