프로그래머스 레벨2 - 멀쩡한 사각형 with Java

문제 설명

 

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

제한사항

W, H : 1억 이하의 자연수

입출력 예

W H result
8 12 80

 

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

나의 코드 1

public class Programmers_멀쩡한사각형 {
    class Square {
        private int w;
        private int h;


        public int getW(int i) {
            return w;
        }

        public void setW(int w) {
            this.w = w;
        }

        public int getH(int i) {
            return h;
        }

        public void setH(int h) {
            this.h = h;
        }

        @Override
        public String toString() {
            return "Square{" +
                    "w=" + w +
                    ", h=" + h +
                    '}';
        }

        public long solution() {
            long answer = 1;

            BigInteger b1 = BigInteger.valueOf(w);
            BigInteger b2 = BigInteger.valueOf(h);
            BigInteger gcd = b1.gcd(b2);
            long gcdd = gcd.intValue();

            answer = w * h - (w + h - gcdd);

            return answer;
        }
    }
    public static void main(String[] args) {
        Programmers_멀쩡한사각형 test = new Programmers_멀쩡한사각형();
        Programmers_멀쩡한사각형.Square test2 = test.new Square();
        test2.setH(12);
        test2.setW(8);
        System.out.println(test2.solution());
    }
}

다른 문제들에서 사람들이 푼걸 보니 solution 메소드만 만든 사람이 대부분이었지만, 이렇게 멤버변수를 활용해서 한 사람도 보여 나도 복습할겸 내부클래스를 만들어봤다. 

우선, 위의 코드는 프로그래머스의 몇몇 테스트케이스에선 통과하지 않는다.

기본 원리는 남은 가용가능한 사각형의 개수 = 너비 * 높이 - (너비 + 높이 - 최대공약수) 인데, 원래 사용하려했던 모든 사각형의 수 너비 * 높이에서 너비와 높이를 뺴고 최대공약수를 더하는 것이다. 최대공약수를 더함으로서 중복되어 빠지는 사각형을 한번만 뺼 수 있다. 

라고 생각했으나, 몇몇 테스트케이스에선 안통하는걸보니 아닌것같다...ㅎ

그래도 위의 코드를 짜면서 게터 세터 등등을 복습할 수 있어서 좋았고, 자바에서 최대공약수를 구하는 내장함수 BigInteger를 써볼 수 있었다. 외부클래스 내에 Square라는 내부 클래스를 만들었는데, 내부 클래스는 모르는 개념이어서 외부 클래스 객체만 만들어놓고 어찌해야지 고민하다가 내부 클래스라는 개념을 검색을 통해 조금 공부하고 위의 메인함수와 같은 방식으로 구현했다.

내부클래스를 사용하려면 우선 외부클래스 디폴트 생성자로 객체를 만들고, 다시 외부클래스의 내부클래스용 생성자를 만들어야 한다.

이 객체에 세터를 적용하면 된다.

아래는 검색을 통해 다시 짠 코드이다.

 

나의 코드 2

public long solution() {
            long answer = 0;
            for(int i = 0; i < w; i++){
                answer += (Long.valueOf(h) * i ) / Long.valueOf(w);
            }
            return answer * 2;
        }

편의상 메소드부분만 떼서 올렸다.

이 로직은 앞서 최대공약수를 활용한 것과는 완전 다르게, 사각형과 직선을 1차함수로 보고 그 기울기와 x에 따른 y값을 이용해서 푼 것이다. 이 코드로는 프로그래머스의 모든 테스트케이스를 통과할 수 있었다. 나는 네모들을 좌표로 볼 생각을 아예 못했다. 기발하다...

중학교 2학년때 배웠던 기울기 공식을 간신히 생각해냈다.

기울기 = 수직 / 수평, 즉 y좌표 / x좌표다.

문제 입출력 예시로 나온 수직 12 수평 8로 생각해보면 기울기는 12/8 즉 4/3이 되는 것이다. 

그래서 y = 4/3 * x 라는 1차함수가 전체 사각형의 양 대각점을 이은 선이 된다.

 

그래서 문제 예시로 나온 그림을 보면, 1차함수화하기위해 그림을 90도 회전했다. 즉, 이 그림의 경우 w = 12, h = 8이 된다.

x좌표가 1일때 함수 식에 대입해보면 y = 8/12 * 1, 즉 0과 1 사이의 소수가 되는데 사용할 수 있는 사각형은 함수선이 지나가기만 해도 안되니 0개다. 즉, 8/12*1보다 작은 최대의 자연수, 0이 된다.

x에 7을 대입해보자. y = 8 / 12 * 7로, 4.xx가 된다. 즉, x가 7일때 사용할 수 있는 사각형은 최대 4개인 것이다.

 

그래서 반복문을 사용해서 x값에 차례대로 0부터 입력인자 w까지 기울기와 w를 곱한 몫을 구해 모두 차곡차곡 더하면 함수선의 한쪽 상자의 개수를 구할 수 있다. 리턴해줄때는 *2를 해줘야 양쪽 모두의 상자의 개수를 구할 수 있다.

 

이때 또 한가지 중요한 점은, 입력인자의 최대값이 2억이기 때문에 Long.valueOf()를 활용해 입력인자 w와 h를 모두 long타입으로 바꿔줘야 메모리 효율이 올라간다는 것이다. 난 BigInteger같은 내장클래스를 쓰면 더 속도가 빠르고 효율도 올라갈거라 생각했는데, 아니었다.