[Java] 프로그래머스(level-2) - 카펫

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

입출력 예시

Input-1
brown=10
yellow=2
Output-1
[4,3]

Input-2
brown=8
yellow=1
Output-2
[3,3]

Input-3
brown=24
yellow=24
Output-3
[8,6]

문제 풀이

---

brown과 yellow의 약수를 활용해 접근하였다.

왜 약수를 통해 접근하였을까?
brown을 b, yellow를 y라 하고 가로크기를 w, 세로크기를 h라 하자.
b+y 값은 w와 h의 곱과 같음을 알 수 있다.

b b b b 
b y y b
b b b b
- b=10, y=2, b+y=12
- w=4, h=3, w*h=12

b b b
b y b
b b b
- b=8, y=1, b+y=9
- w=3, h=3, w*h=9

b b b b b b b b
b y y y y y y b
b y y y y y y b
b y y y y y y b
b y y y y y y b
b b b b b b b b
- b=24, y=24, b+y=48
- w=8, h=6, w*h=48

그리고 b와 y는 b+y의 약수중 하나의 수로 구성되어 있다. b+y의 약수들 중에 w와 h를 찾으면 된다.

w와 h 구하기

b+y를 sum이라 하면, sum의 약수들을 구하고 sum만큼 반복하며 sum과 두 약수의 곱이 같을 때 두 약수가 w와 h가 된다.

그런데, 아래 예를 보자.

b=10, y=2, sum=12, divisor=[1,2,3,4,6,12] 일 떄
i=1이면, 1*12 = 12
i=2이면, 2*6 = 12
i=3이면, 3*4 = 12
...

각 i별로 매칭되는 i를 곱하면 모든 수가 sum의 약수이기에 모두 sum을 구할 수 있다.
그렇기에 가로와 세로크기를 구할 때 아래 식을 검증해야 한다.

• (w-2)(h-2) = yellow

w와 h에 각각 2를 빼고 곱한값이 세로크기 즉, yellow 값이 되어야 한다.
이 식을 대입해서 생각해보면 (w-2)(h-2) == 6을 만족해야 한다.

i=1이면, (1-2)*(12-2) = -10
i=2이면, (2-2)*(6-2) = 0
i=3이면, (3-2)*(4-2) = 2 (=yellow)

위와 같이 i가 3일 때 조건을 만족하는 것을 알 수 있다.

이제 카펫의 가로와 세로크기를 구하는 방법을 알았으니, 코드로 작성해보자.

ArrayList<Integer> div = new ArrayList<>(); // 약수를 담을 리스트
int sum = brown+yellow; // brown+yellow
int[] answer = new int[2]; // return 배열

for(int i=1; i<=sum; i++) {
    if(sum%i == 0) div.add(i); // 약수만 div에 저장
}

약수들을 담을 ArrayList div 리스트, brown과 yellow의 합을 담을 sum 변수, 가로크기와 세로크기를 담아 반환할 answer 배열을 초기화하였다.
그리고 sum만큼 반복하며 약수들을 div에 담았다. 이때, 약수를 담을 div를 int배열로 만들지않고 ArrayList로 선언한 이유는, 약수의 개수를 미리 알 수 없기 때문이다.

for(int i=0; i<=div.size()/2; i++) { // div의 반만큼만 반복
    if((div.get(i)-2)*(sum/div.get(i)-2) == yellow) {
        answer[0] = sum/div.get(i);
        answer[1] = div.get(i);
        break;
    }
}

약수리스트인 div의 반만큼만 반복해도 [sum/현재약수] 하여 모든 약수를 알 수 있다
반복문 내에서 각 약수마다 (w-2)(h-2)==yellow 식을 검증하여 가로크기와 세로크기를 구했다.

작성 코드

---

import java.util.*;

class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int b = sc.nextInt();
        int y = sc.nextInt();
        
        long start = System.currentTimeMillis();
        solution(b,y);
        long end = System.currentTimeMillis();
        System.out.println("\n수행시간 = " + (end-start));
    }

    public static int[] solution(int brown, int yellow) {
        ArrayList<Integer> div = new ArrayList<>();
        int sum = brown+yellow;
        int[] answer = new int[2];

        for(int i=1; i<=sum; i++) {
            if(sum%i == 0) div.add(i);
        }

        for(int i=0; i<=div.size()/2; i++) {
            if((div.get(i)-2)*(sum/div.get(i)-2) == yellow) {
                answer[0] = sum/div.get(i);
                answer[1] = div.get(i);
                break;
            }
        }
        
        return answer;
    }
}

회고

• 약수를 활용해 접근하는 것까지는 하였지만, (w-2)(h-2)==yellow 식을 떠올리기가 힘들었다. 특정 수를 구할 수 있는 식을 많이 세워봐야한다.