프로그래머스 멀쩡한 사각형 - 자세한 풀이 (Java)

🧩 문제 정보

• 문제: https://school.programmers.co.kr/learn/courses/30/lessons/62048#
• 난이도: LV 2
• 유형: 구현, 수학

NewCodes의 풀이

• 스스로 풀었는가: X
• 다시 풀어볼 문제인가: O
• 풀이 시간: 60분 + a
• 제출 횟수: 7회
• 선택 언어: Java
• 풀이 환경: 프로그래머스 내 IDE

---

📝 풀이 정보

요구 사항 정리

1. 대각선에 의해 관통되는 정사각형은 제외해야 한다.
2. 가로 길이와 세로 길이는 1억 이하의 자연수이다.

 

풀이 설계

 : 구글링해보니 다들 수학적으로 푸신 것 같은데, 저는 구현 위주로 접근하여 풀이했습니다. 

입출력 예를 통해 큰 직사각형 안에서 관통된 직사각형 부분이 똑같은 패턴으로 반복되는 걸 발견했습니다. 그래서 가장 최소 단위의 패턴을 알고 총 패턴이 몇 개 있는지만 알면 문제를 쉽게 풀어낼 수 있을 거라 생각했습니다. 

 

하지만, 각 패턴에 대해서 어떻게 관통된 정사각형 개수를 세야할 지 감이 잘 안 왔습니다. 그래서 우선은 가로에서 1만큼만 움직이면서 관통된 직사각형 개수를 세고자 했습니다. 또한, 기울기를 이용하여 각 좌표를 파악하고자 했습니다. 

 

이렇게 하면 가로의 폭이 1일 때, y 좌표의 차를 통해 관통된 정사각형의 개수가 몇 개인지 가늠할 수 있습니다. 

 

대각선이 가로 1 단위만큼 갔을 때, 생기는 케이스는 크게 세 가지였습니다. 그리고 각 경우에 따라 관통된 정사각형의 개수는 다음과 같습니다. 

1. 둘 다 정수인 경우 -> y좌표 차
2. 둘 중 하나가 정수인 경우 -> Math.ceil(y좌표 차)
3. 둘 다 정수가 아닌 경우 -> Math.ceil(큰 y 좌표) - Math.floor(작은 y 좌표)

이를 이용하여 저는 아래와 같이 풀었습니다. 

 

실전 풀이 - 구현

class Solution {
    public long solution(int w, int h) {
        long answer = (long) w * h;
        long nonUsed = 0;
        
        // w와 h의 최대 공약수로 서로 나누어주면 성능 향상 가능!
    
        double m = (double) h / w; 
        double beforeY = 0;
        double afterY = m;
        
        for (int i = 0; i < w; i++) {
            if (beforeY % 1 == 0.0 && afterY % 1 == 0.0) {
                nonUsed += (long) (afterY - beforeY);
            } else if (beforeY % 1 == 0.0 || afterY % 1 == 0.0) {
                nonUsed += (long) Math.ceil(afterY - beforeY);
            } else {
                nonUsed += (long) Math.ceil(afterY) - (long) Math.floor(beforeY);
            }            
            
            beforeY = afterY;
            afterY = (double) h * (i + 2) / w;
        }
        
        answer -= nonUsed;
        
        return answer;
    }
}

 

 

풀이 시행 착오

1. int 연산 시 long, double 형변환

long answer = (long) w * h; // (long) 빼 먹음

double m = (double) h / w; // (double) 빼 먹음

 

형변환을 제대로 하지 않아서 제출 실패를 여러 번 했었습니다 ㅠㅠ

 

h, w는 int이지만 경우에 따라 int의 제한 범위를 넘을 수 있습니다. 이를 방지하기 위해 (double)을 통해 형변환을 해줘야 했습니다. h가 int에서 double로 형변환 되면, w는 묵시적 형변환이 이루어집니다. 

 

기울기 m을 정확히 구하기 위해서는 'h / w' 연산 결과 소수점이 나올 수도 있기에 미리 double로 형변환이 이루어져야 합니다. 

 

 

2. double 연산 오류

// 처음에 afterY 좌표를 갱신한 수식 (실패)
afterY += m;

// 두 번째로 고려한 방식 (실패)
afterY = m * (i + 2); 

// 마지막 방식 (성공)
afterY = (double) h * (i + 2) / w;

 

부동 소수점 오차로 인해 답이 다르게 산출됐습니다. 이거 개념만 들어봤지, 실제로 제가 문제 해결에 영향을 받은 경험은 처음이네요. 

 

해결 방법은 연산 순서를 바꾸어줬더니 통과했네요. 왜 이러한 연산 순서로 해야 오차가 줄어드는지 이해는 잘 안 되네요. 부동 소수점에 대해서 더 공부해 보고 해결해봐야 할 것 같습니다. 

 

 

풀이 의도 설명

 : 제 풀이에서의 포인트는 크게 세 가지입니다. 

 

1. '전체 정사각형 개수'에서 '대각선에 의해 관통된 정사각형 개수'를 빼는 방식으로 정답 도출

 : 대각선에 의해 잘라지지 않은 사각형을 직접적으로 바로 구하는 건 다소 복잡할 거라고 생각했습니다. 그래서 전체에서 손상된 부분을 빼는 방식을 채택했습니다. 

 

2. x를 1만큼 움직이면서 대각선의 기울기를 통해 y 좌표 구하기

 : 문제에서 주어진 직사각형에 대해 가로길이 1만큼을 한 단위로 인식하여, 각 단위에서 대각선에 의해 관통된 정사각형이 몇 개인지 구하고자 했습니다. 이를 위해서는 가로길이가 1인 단위의 직사각형에서 '관통이 시작된 y 좌표(beforeY)', '관통이 끝난 y 좌표(afterY)' 두 좌표가 필요합니다. 관통이 시작된 y 좌표가 있다면 기울기를 통해 나머지 y 좌표도 구할 수 있습니다. 

 

3. 두 y 좌표를 통해서 세 가지 케이스로 나눠 관통된 정사각형 개수 구하기

 : 두 y 좌표를 구했다면, 해당 좌표를 통해서 관통된 정사각형 개수를 구할 수 있습니다. 두 y 좌표의 상태는 크게 세 가지 케이스로 나뉩니다. 아래에 각 케이스에 따라 관통된 정사각형 개수도 표기했습니다. (단, 기울기는 양수, beforeY < afterY)

1) 둘 다 정수인 경우 -> afterY - beforeY
2) 둘 중 하나가 정수인 경우 -> Math.ceil(afterY - beforeY)
3) 둘 다 정수가 아닌 경우 -> Math.ceil(afterY) - Math.floor(beforeY)

 

위와 같이 케이스를 분류해 가며 총 가로길이(W)만큼만 반복하면 관통된 직사각형의 개수를 모두 구할 수 있습니다. 

 

 

정돈된 풀이 - 수학

 : 이번엔 규칙성을 파악하여 구현 풀이보다 더욱 좋은 효율로 풀어봤습니다. 단, 최대 공약수를 구할 때 저는 완탐으로 구했지만, 유클리드 호제법으로 더욱 시간 효율을 챙길 수도 있습니다. 

class Solution {
    public long solution(int w, int h) {
        int gcd = getGCD(w, h);
        long nonUsed = (w / gcd + h / gcd - 1) * gcd;
        long answer = (long) w * h - nonUsed;
        
        return answer;
    }
    
    public static int getGCD(int w, int h) {
        int min = Math.min(w, h);
        int gcd = 1;
        
        for (int i = 1; i <= min; i++) {
            if (w % i == 0 && h % i == 0) {
                gcd = i;
            }
        }
        
        return gcd;
    }
}

 

---

🎯 풀이 피드백

• 처음 풀이 설계할 때 케이스 나눠서 생각하는 방식 염두에 두기!
• 절차적으로만 문제를 바라볼 게 아니라 규칙성을 파악하려는 것도 중요하다! (특히, 도형 위주로 이루어진 상황이니 규칙성이 생길 수밖에)
• int 연산 시 double, long로의 형변환 고려하기!
• 더 학습할 것
  • 유클리드 호제법 학습하기
  • 부동 소수점 학습하기