프로그래머스 Lv.2) 멀쩡한 사각형

멀쩡한 사각형

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

풀이

평소에 레벨 3,4 혹은 카카오 문제를 풀어왔기에 레벨 2는 쉽다고 생각하며 접근했다가 큰코다쳤다. 너무너무 어려웠고 푸는데 오랜 시간이 걸렸다.

먼저, 처음에 생각했던 로직은 직선이 타일과 정수 좌표에서 만나는 구간을 구해 반복되는 만큼 수를 빼주는 것이었다.

그래서 Linear Equation(1차 방정식)을 세우고 해당 직선과의 거리를 구하면서 진행했다.

정수인 x,y 점을 돌면서 루트 2(sqrt 2)보다 작으면 쓸 수 없는 사각형으로 카운트를 세주었고, 거리가 0이 되는 점이 두 번 나왔다면 반복문을 종료했다. 이후, 거리가 0이 된 두 점이 늘어난 길이만큼 전체를 돌면서 몇개의 구간이 반복되는지 세주었고, 앞서 구했던 쓸 수 없는 사각형 카운트에 반복되는 구간의 수를 곱해준 만큼 빼줘서 답을 구했다. 이 때, 곱하기 전에 쓸 수 없는 사각형의 갯수는 /2를 해주었다. (정수 점을 돌다보면, 1x1 사각형의 두 점을 체크하기 때문이다.

하지만, 당연하게도 이 풀이는 3문제 정도인가? 시간초과가 뜨면서 고치기를 포기했다. 왜냐하면 이 로직을 고수하면서 빠르게 만들 수 없기 때문이다.

처음 생각한 방식

이후 생각한 것은 '직선을 구했는데 모든 점을 셀 필요가 있을까?' 였다. 그래서 생각한 것은 y축의 점만 돌면서 직선 오른쪽에 사용 가능한 사각형 갯수를 구하는 것이었다. 그렇게되면 전체 사각형에서 절반만 체크해 준것이니까 x2를 통해 전체 사각형에서 사용가능한 갯수를 구해주었다.

두번째 로직

맞았다고 생각했는데 테스트케이스 6번이 실패로 떴었다. 로직에는 문제가 없는데 뭐가 문제지 생각하다가 위의 사용 가능한 사각형을 구할 때, y축의 정수 지점을 돌면서 그에 해당하는 x좌표를 직선 식을 통해 구했다. 위의 그림에서 보다시피 직선이 정수 y와 마주하는 x는 실수형이고, 실수를 통해 연산을 하는 것이었다. 아주 감사하게도 문제의 질문하기에 나와 똑같이 고생했던 분이 계셨고, double형의 연산이 누적되다보면 반환값의 오류가 생길 수 있다는 것이었다. 자바스크립트의 입실론 개념을 떠올려 x값을 리턴할 때부터 사용 가능한 x지점을 정수형으로 반환해주었고 통과할 수 있었다.

 

어제 풀면서 했던 고민의 과정을 적어 내려가다보니 두서도 없고 맺음말도 어떻게 해야할지 모르겠다. 그만큼 쉽게 봤던 문제에 큰 코를 다쳤고, 최근에는 알고리즘에 집중하면서 풀었기 때문에 참신함에 머리가 많이 막혀있음을 느꼈다. 이 문제에 대해 포스팅 하신 분들의 게시물을 봤는데 두 줄만에 끝낸 분도 있었다... ㅠㅠ

 

아무튼 이 문제를 통해 double형의 연산이 많이 누적되다보면 결과값이 다르게 나올 수 있다는 것을 깨우쳤고, 이를 회피하는 로직을 생각하자. 그리고 Math.ulp 라는 새로운 메소드를 알게되어 기쁘다.

 

Math.ulp는 해당 값의 아주 작은 실수의 다음 값? 이라고 했던거 같은데 그냥 입실론 값이라고 생각하기로 했다.

 

코드

public class NormalSquare_62048 {
    private static long solution(int w, int h) {
        return getNumbers(w,h);
    }

    private static long getNumbers(int w, int h) {
        long result = 0;  // 총 사각형 갯수
        for(int y=h-1; y>=0; y--) {
            double x = getX(y, w, h);
            result += w-x;
        }
        result *=2;
        return result;
    }

    private static long getX(int y, int w, int h) {
        double num = (h-y)/((double)h/w);
        long result;
        if(num -(long)num> Math.ulp(num)) {
            result = (long) num+1;
        } else {
            result = (long)num;
        }
        return result;
    }

    public static void main(String[] args) {
        int W =8;
        int H =12;
        System.out.println(solution(W,H));
    }
}