[프로그래머스] 카펫 (구현)

문제 소개

오늘 풀었던 카펫 - 프로그래머스 문제를 정리합니다.
이 문제는 노란색 내부 영역과 갈색 테두리 수를 바탕으로 전체 카펫의 가로, 세로 크기를 유추하는 문제입니다.
핵심은 전체 넓이의 약수쌍 중에서 조건을 만족하는 조합을 찾는 것입니다.

문제 링크: 카펫 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 전체 격자 수 = brown + yellow를 기준으로 (가로, 세로)의 가능한 조합을 탐색
2. (가로 - 2) * (세로 - 2)가 yellow와 일치하는지 확인
3. 조건에 맞으면 해당 (가로, 세로)를 정답으로 반환

---

해결 과정 및 코드

핵심 아이디어

1. 전체 격자 수는 brown + yellow
2. 가로, 세로 조합 중에서 (w - 2) * (h - 2) == yellow가 되는 경우만 정답
   • 내부 영역 = 노란색 타일 개수
   • (w - 2)와 (h - 2)는 양쪽 테두리를 제외한 실제 내부 크기
3. 조건에 맞는 (w, h)를 찾는 방식으로 완전탐색 진행

코드

시간 복잡도 : O(√N)

import java.util.*;

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

        for (int h = 3; h <= total / h; h++) {
            if (total % h != 0) continue; // 나누어떨어지지 않으면 skip

            int w = total / h;

            if ((w - 2) * (h - 2) == yellow) {
                return new int[]{w, h};
            }
        }

        return new int[]{}; // 이론상 여기까지 오지 않음
    }
}

 

참고 : 조건 설명

1. h = 3부터 시작하는 이유

• 노란색 영역은 테두리 안쪽에 존재
• 즉, 세로 ≥ 3이어야 (h - 2)가 최소 1 이상이 되어 내부 공간이 생김
• h = 1이나 h = 2는 내부 공간이 없거나 음수가 되므로 무시

2. (w - 2) * (h - 2) == yellow

• 전체 카펫에서 갈색 테두리 1줄을 제외한 내부 공간은 (w - 2) * (h - 2)
• 이 내부 공간이 바로 yellow 개수와 일치해야 함
• 조건을 만족하면 해당 (w, h)가 정답

3. h <= total / h

• (h, w) 쌍과 (w, h) 쌍은 동일한 의미이므로 중복 방지
• w = total / h이므로 h > total / h가 되는 순간부터는 이전에 확인한 조합이 반복됨
• 이 조건을 통해 약수 쌍 탐색을 절반으로 줄이고 불필요한 연산 방지