[Java] 프로그래머스 - 카펫

전체 칸 수의 약수쌍을 구한 뒤, 테두리를 제외한 내부 넓이가 yellow가 되는 가로·세로를 찾는 문제

 

1. 문제 유형

완전탐색, 수학, 구현

 

2. 내가 놓친 포인트

처음 떠올린 접근 : 갈색 칸 수를 직접 세면서 가로와 세로 규칙을 찾으려고 했다.

오답 원인: 전체 넓이와 내부 노란색 넓이의 관계를 식으로 바꿔서 봐야 했다.
처음에는 brown 개수 변화만 보고 규칙을 찾으려 해서 접근이 길어졌다.

 

3. 핵심 로직 & 해결 방법

핵심 조건: 전체 넓이의 약수쌍 중에서 테두리 1줄을 뺐을 때 내부 넓이가 yellow가 되는 가로·세로를 찾아야 한다.

풀이 아이디어:

1. 전체 칸 수 all = brown + yellow 를 구한다.
2. 전체 칸 수의 약수쌍을 구한다
3. 가로가 세로보다 같거나 클때 (가로 - 2) * (세로 - 2) == yellow인 것을 찾는다.

4. 구현 코드

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = {};
        int all = brown + yellow;

        for (int i = 1; i <= Math.sqrt(all); i++) {
            if (all % i == 0) {
                int height = i;
                int width = all / i;

                if ((width - 2) * (height - 2) == yellow) {
                    answer = new int[]{width, height};
                    break;
                }
            }
        }

        return answer;
    }
}

시간 복잡도: O( √ N) / 공간 복잡도: O(1)

 

---

 

인사이트

• 약수쌍을 구할 때는 `1`부터 `N`까지 전부 볼 필요가 없고, `√N`까지만 확인하면 된다.
• 이 문제처럼 직사각형의 가로·세로를 찾는 문제는 전체 넓이의 약수쌍을 먼저 떠올리는 습관이 중요하다.
• 혼자서 못 푼 문제고 최소 2번 복습할 것.

 

 

문제 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/42842