[알고리즘/프로그래머스] 멀쩡한 사각형

Summer/Winter Coding(2019) > 멀쩡한 사각형 / level2

 

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

 

나의 풀이

 

접근방법

 

1. 가로/세로 길이 W, H의 최대공약수를 구한다.

예시 그림을 보면 2*3 사각형이 4개 반복되면서 규칙적으로 있는 모습이다.

2*3은 가로가 8, 세로가 12인 사각형의 최대공약수인 4로 나눠준 수이다.

여기서 힌트를 얻어 최대 공약수를 구해 사용하였다.

(gcd 함수 사용하지 않고 그냥 구했음)

 

m = min(w, h)
while m >= 1:
    if w%m == 0 and h%m == 0:
        break
    m-= 1

 

 

2. 선에 의해 가려지는 사각형의 규칙 찾기

경우 3과 경우 4에 대해서 최대 공약수로 나눠 준 가장 작은 사각형에서 그어 준 선 기준 중심 좌표 활용

 

경우 1. 정사각형인 경우

가로=세로 의 길이 개수만큼 선이 사각형을 지난다.

4*4 --> 4

3*3 --> 3

 

경우 2. 가로 또는 세로의 길이가 1인 경우 (테스트케이스 1번이 틀릴 경우)

선이 모든 사각형을 지난다.

1*9 --> 9

1*3 --> 3

1*1 --> 1

 

경우 3. 중심 좌표값의 X와 Y 값의 합이 정수가 아닌 경우

(중심 좌표가 선에 위치)

위의 예시에서와 같이 2*3 사각형인 경우

중심 좌표값이 (1, 1.5) 이다. 이때 선이 4개의 사각형을 지난다.

중심 좌표값의 정수값 1(1)과 1(1.5)을 더한 후 2를 곱해주면 4가 된다.

2*3 --> 4

 

 

경우 4. 중심 좌표값의 X와 Y 값의 합이 정수인 경우 (테스트케이스 5번이 계속 틀렸던 이유)

(중심 좌표가 사각형 안에 위치)

3*7 사각형의 경우 중심 좌표값이 (1.5, 3,5) 이다.

경우 3처럼 중심 좌표값의 정수 값 1(1.5), 3(3.5)를 더한 후 2를 곱해주면 8이 된다.

하지만 이 경우에는 중심 좌표가 위치한 사각형을 체크하지 못하기 때문에 1을 추가로 더해주어야 한다.

그래서 만약 중심 좌표값의 합이 정수인 경우는 1을 추가로 더해주었다.

(isnumeric 함수를 사용해보려고 했는데 잘 못해서 값 비교로 해줌)

3*7 --> 9

 

 

if s_w == 1 or s_h == 1:         #경우 2
        answer = max(s_w, s_h)
elif s_w == s_h:                 #경우 1
    answer = s_w
else:
    answer = (s_w//2+s_h//2) * 2       #경우 3
    if (s_w/2 + s_h/2) == int(s_w/2 + s_h/2):   #경우 4
        answer += 1

 

---

 

최종 제출 코드

 

def solution(w,h):
    m = min(w, h)
    while m >= 1:
        if w%m == 0 and h%m == 0:
            break
        m-= 1
    s_w, s_h = w//m, h//m
    
    if s_w == 1 or s_h == 1:
        answer = max(s_w, s_h)
    elif s_w == s_h:
        answer = s_w
    else:
        answer = (s_w//2+s_h//2) * 2
        if (s_w/2 + s_h/2) == int(s_w/2 + s_h/2):
            answer += 1

    return w*h - answer*m

 

---

 

다른 사람의 풀이

(이거 보니까 내 풀이 ,, 너무 길어,, ㅎ)

 

def gcd(a,b): return b if (a==0) else gcd(b%a,a)    
def solution(w,h): return w*h-w-h+gcd(w,h)

이해가 잘 안되서 풀이 밑에 달린 댓글을 가지고 옴 (그래도 헷갈리는게 함정..)

 

교점 수=반복되는 횟수=(최대공약수)/ 교점이 없을 때 대각선이 뚫는 사각형 개수

=(가로'+세로'-1)/ (가로'+세로'-1)*(최대공약수)

=(가로+세로-최대공약수)

답: 전체사각형 개수-(가로+세로-최대공약수)

 

from math import gcd
def solution(w,h):
    return w * h - (w/gcd(w, h) + h/gcd(w, h) - 1) * gcd(w, h)