[프로그래머스] 카펫 - Java (완전탐색 & 수학적 최적화)

📝 문제 설명

갈색 격자(brown)와 노란색 격자(yellow)의 수가 주어질 때, 카펫의 가로, 세로 크기를 구하는 문제입니다.

• 카펫의 가로 길이는 세로 길이보다 길거나 같습니다.
• 테두리 1줄은 갈색이며, 그 안쪽은 모두 노란색입니다.

---

💡 접근 방식

1. 기하학적 수식 도출

카펫의 가로를 w, 세로를 h라고 정의하면 다음과 같은 두 가지 식을 도출할 수 있습니다.
1. 전체 면적: $w \times h = brown + yellow$
2. 노란색 면적: 테두리를 제외한 안쪽 크기이므로 $(w - 2) \times (h - 2) = yellow$

2. 탐색 범위 최적화 ($O(\sqrt{N})$)

전체 격자 수(sum)는 최대 2,000,000입니다. 모든 경우의 수를 다 조사하는 대신, 약수의 성질을 활용했습니다.

• 세로의 최소치: 노란색 격자가 1칸이라도 있으려면 세로는 최소 3 이상이어야 합니다.
• 제곱근 활용: $w \ge h$ 조건에 따라 세로 $h$는 전체 면적의 제곱근($\sqrt{sum}$)을 넘을 수 없습니다. 이를 통해 탐색 범위를 획기적으로 줄였습니다.

3. 검증 로직

1. h를 3부터 Math.sqrt(sum)까지 순회하며 sum의 약수인지 확인합니다.
2. 약수라면 가로 w = sum / h를 구합니다.
3. 도출한 w와 h를 노란색 면적 공식에 대입하여 일치하면 즉시 반환합니다.

---

💻 구현 코드

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

    int sum = brown + yellow;
    for(int h = 3; h <= Math.sqrt(sum); h++) {
        if(sum % h == 0) {
            int w = sum / h;
            
            if((w-2) * (h-2) == yellow) {
                return new int[] {w, h};
            }
        }
    }
    
    return answer;
}

}

---

✨ 느낀 점

✅ 시간 복잡도의 중요성단순히 이중 루프로 모든 조합을 찾는 것($O(N^2)$)과 약수의 원리를 이용해 탐색 범위를 줄이는 것($O(\sqrt{N})$)의 차이를 명확히 체감했습니다. 데이터 범위가 커질수록 수학적 접근이 얼마나 강력한지 알 수 있었습니다.

✅ 문제의 추상화도형의 배치를 가로, 세로의 관계식으로 변환하는 과정에서 문제를 추상화하는 능력을 기를 수 있었습니다. 특히 "테두리를 뺀다"는 개념을 -2라는 수식으로 치환하는 로직이 인상적이었습니다.

✅ 효율적인 데이터 관리BFS나 DFS 같은 복잡한 알고리즘 없이도, 문제의 제약 조건을 잘 파악하면 훨씬 단순하고 빠른 코드를 짤 수 있다는 것을 배웠습니다.