[프로그래머스] 카펫

programmers.co.kr/learn/courses/30/lessons/42842

코딩테스트 연습 - 카펫

 

문제는 위와 같으며, 짧은 수식을 통해 문제를 해결할 수 있겠지만... 거기까지 생각하지 못해 아래와 같이 풀이하였습니다...ㅠ

 

1. 전체 카펫의 넓이를 구합니다. (brown + yellow)

2. 카펫의 넓이를 구하기 위한 3이상의 가로, 세로 값을 모두 구합니다.

    -> 카펫 넓이의 약수들을 구해서 더 큰 수(가로)를 key, 작은 수(세로)를 value로 하는 Map 형태로 저장하였습니다.

3. 약수의 모음을 하나씩 확인하면서 양옆과 위아래를 뺀 수의 곱이 yellow와 같은지 비교하고 같다면 정답을 반환합니다.

 

자바 코드는 다음과 같습니다.

import java.util.*;

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];

        Map<Integer, Integer> divisors = getDivisor(brown + yellow);
        
        // 구한 약수(가로:세로)들을 하나씩 확인하면서
        for (Map.Entry<Integer, Integer> divisor : divisors.entrySet()) {
            int w = divisor.getKey();
            int h = divisor.getValue();

            // 양옆과 위아래를 하나씩 뺀 사각형의 넓이가 yellow와 같다면 정답 반환
            if ((w - 2) * (h - 2) == yellow) {
                answer[0] = w;
                answer[1] = h;
                break;
            }
        }

        return answer;
    }
    
    // 약수 구하기
    private static Map<Integer, Integer> getDivisor(int num) {
        // 가로(더 큰 수)를 key로 하고 세로(더 작은 수)를 value로 하는 Map
        Map<Integer, Integer> divisors = new TreeMap<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

        // 약수 구하기
        for (int i = 3; i < num / 2; i++) {
            if (num % i == 0) {
                int key = Math.max(i, num / i);
                int val = Math.min(i, num / i);

                if (divisors.containsKey(key) || divisors.containsKey(val)) {
                    break;
                }

                divisors.put(key, val);
            }
        }

        return divisors;
    }
}