[프로그래머스] 멀쩡한 사각형

문제를 풀면서 항상 느끼는 거지만 나는 다른 사람들과 문제를 약간 다르게 푸는 것 같다ㅠ

 

하지만 뭐 방법이 뭐든 간에 도착지점에 가기만 하면 만사 오케이!!👍

 

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

 

해당 문제는 간단한 문제로 예시만 봐도 문제 파악이 가능하다.

 

입출력 예

W                                                  H                                                 result

8

12

80

입출력 예 설명

입출력 예 #1
가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80을 반환합니다.

 

그림만 봐도 w*h만큼 사각형을 생성하고

왼쪽 상점에서 오른쪽 하점까지 직선으로 선을 그어 선에 닿는 사각형의 개수를 제외하고 Return 하는 문제이다.

 

내가 생각한 풀이 방법

나는 처음 보자마자 점에 집중을 했는데 최대한 빠르게 진행하려고 한다면 규칙이 되는 점을 찾고 그 점의 사각형의 개수에서 곱하면 된다고 생각했다.

그래서 생각한 방법이 위에 사진에 좌표로 치자면 (2,3)처럼 정수로 딱 떨어지는 점을 기준까지의 사각형 개수를 세고 전체 x의 길이에서 진행한 x좌표의 길이를 나눈 만큼 사각형의 개수에 곱해주는 형식으로 진행했다. 

예를 들면 위에 예시에서는 전체 x의 길이는 8이고 내가 생각한 기준점은 x좌표가 2일 때까지 진행됐다. 

그럼 사각형의 개수는 4이고 8(전체 x의 길이)/2(진행된 x좌표)=4이니 16(4(기준점까지 사각형 개수)*4(전체 x의 길이/진행된 x좌표))이 선에 닿는 사각형의 개수라고 생각했다.  

 

왜?

w, h의 조건이 1억 이하의 자연수였고 숫자가 너무 크면 시간 초과가 날것이라고 생각하여 해당 방법으로 진행했다.

 

 

그런데!!!

문제가 생겼다.

코드를 다 짜고 돌려보니 6번만 Failed 났고 print 하여 원인을 찾아보니 이상한 점이 있었다.

 

손가락으로 가리킨 곳은 0.999999999999가 아닌 1이 나와야 했다.

 

궁금해서 계산기로 계산해봤는데 1이 나왔고 프로그래머스에서 해당 수식을 그냥 프린트해봤는데 0.999999999999.... 가 나왔다!!😅

 

이게 어찌 된 건지...

 

너무 궁금한 나머지 질문하기에 들어가서 이유를 찾아본 결과

사칙연산 순서에 따라 값이 달라진다고 한다...!

 

나누기를 먼저 하면 소수점이 버려진 후 곱하기를 하기 때문에 미세하지만 오차가 생긴다고 한다.

그런 미세한 오차로 인해 눈덩이가 되어 돌아왔다!

 

결국 조란님의 도움을 받아 사칙연산을 바꾸었고 코드를 완성할 수 있게 되었다!

 

코드

import math
def solution(w,h):
    first,value,temp=0,0,0
    
    if w>h: # w의 값이 크면 서로 바꾸기 w를 기준으로 도는거라 상대적으로 작은값 셀렉
        temp=w
        w=h
        h=temp
    
    for i in range(1,w+1):
        value=value+math.ceil(i*h/w)-int(first)#y좌표를 통해 사각형 개수 세기.
        
        first=i*h/w #다음 루틴을 위해 기준 y좌표 값이 변경  
        
        if i*h/w==int(i*h/w): # 기준 점에 닿으면 break 
            break
            
    value=value*(w/i) #w->전체의 x의 길이 i->진행된 x의 길이 value->사각형의 개수 
    
    return w*h-value 

 

실행결과

아니 근데 왜 이렇게 실행시간이 길게 나왔지?ㅋㅋㅋㅋㅋㅋㅋㅋㅋ