멀쩡한 사각형

유태형·2022년 3월 17일

코딩테스트 프로그래머스

프로그래머스 - Level 2

목록 보기

32/36

문제

문제 분석

수학적으로 접근해야하는 문제입니다. 사각형과 대각선을 이용하여 구해보겠습니다. 다른방법도 있을 듯 합니다.

풀이

x값,y값,기울기 이용
자바 자료형의 한계
대각선을 제외한 사각형

x값,y값,기울기 이용

기울기 = x / y으로 기울기는 같은 도형내에서 어느 x든 y든 항상 상수입니다.

		double angle = (double) h / (double) w; //기울기
        
        for(int x = 1;x <= w;x++){
            double y = x * angle; //x +1당 y의 위치       
            long temp = (long)Math.ceil(y) - prev; //y칸으로 몇칸 이동했는지
            answer += temp; //더하고
            prev = (long)Math.floor(y); //다음 x위해 내림함
        }

x축이 +1씩 할때마다 기울기를 이용하여 y축을 구하였습니다.

소수점을 언제 왜 올려야하느냐가 이 문제에서 중요한 구분 기준이 됩니다. 대각선으로 걸쳐져 있다면 해당 사각형은 포함되어야 합니다.
(Long)Math.ceil(y)를 보시면 소수점으로 넘어가더라도 포함시키 위해 올림 하였고, 마찬가지로 (long)Math.floor(y)를 보시면 다음 x축때 기준으로 잡고 포함시키기 위해 내림하였습니다.

자바 자료형의 한계

논리적으론 아무문제가 없는 풀이가 막상 테스트 케이스 6번에서 오류를 발생하게 됩니다. 당황스러워서 여러 다른 블로그나 질문을 찾아보니 자바의 double의 부정확함에서 오류가 발생하게 되는 것 입니다.

		for(int x = 1;x <= w;x++){
            double y = (double)h * x / w; //x +1당 y의 위치(double형식의 정확도 문제로 h부터)      
            long temp = (long)Math.ceil(y) - prev; //y칸으로 몇칸 이동했는지
            answer += temp; //더하고
            prev = (long)Math.floor(y); //다음 x위해 내림함
        }

기울기와 x를 이용하여 y를 구하는 부분에서 순서를 약간 수정했습니다.
원래대로라면 y = x 기울기(높이/너비) 이어야 하지만 , y = 높이 x / 너비로 순서를 조정하여 오버헤드가 발생하는 경우를 최소화 하였습니다.

대각선을 제외한 사각형

대각선에 포함되지 않은 사각형 = 전체 사각형 - 대각선에 포함된 사각형

return (long)w * h - answer; //대각선 제외 사각형

코드

class Solution {
    public long solution(int w, int h) {  
        if(w <= 1 || h <= 1) //높이가 1이하기억나 너비가 1이하인 경우 모든 사각형이 대각선에 포함
            return 0;
    
        long answer = 0;
        long prev = 0; //이전 y위치
        
        for(int x = 1;x <= w;x++){
            double y = (double)h * x / w; //x +1당 y의 위치(double형식의 정확도 문제로 h부터)      
            long temp = (long)Math.ceil(y) - prev; //y칸으로 몇칸 이동했는지
            answer += temp; //더하고
            prev = (long)Math.floor(y); //다음 x위해 내림함
        }
        
        return (long)w * h - answer; //대각선 제외 사각형
    }
}