[프로그래머스 / Java] Lv.2 카펫 - 연습 문제 (1) with ChatGPT

📘 연습 문제  :  액자 만들기

 

문제 설명

정사각형 타일로 직사각형 액자(프레임)를 만들려고 합니다.

• 액자의 테두리(1칸 두께)는 frame개의 타일로 구성됩니다.
• 액자 내부(테두리를 제외한 안쪽)는 center개의 타일로 구성됩니다.
• 액자의 가로 길이를 W, 세로 길이를 H라고 할 때
  • W ≥ H
  • H ≥ 3, W ≥ 3 (테두리가 존재하려면 최소 3 이상)

frame과 center가 주어질 때, 액자의 [가로 W, 세로 H]를 구하세요.
정답은 항상 1개만 존재합니다.

---

예시

• frame = 24, center = 24
• 전체 = 48
• 후보 (W, H) 중에서 (W-2)(H-2)=center 만족 → [8, 6]

---

Algorithm

1. 전체 타일 수 total = frame + center를 계산한다.
2. 세로 길이 H를 3부터 가능한 범위까지(보통 √total까지) 하나씩 시도한다.
3. total % H == 0이면 가로 후보 W = total / H를 구한다.
4. W ≥ H 조건을 만족하는지 확인한다.
5. 내부 타일 조건인 (W - 2) * (H - 2) == center를 만족하면 [W, H]가 정답이다.
6. 정답을 반환한다.

---

Code

class Solution {
    public int[] solution(int frame, int center) {
        int total = frame + center;

        for (int h = 3; h * h <= total; h++) { // h는 세로 후보 (최소 3)
            if (total % h != 0) continue;      // 나누어 떨어져야 직사각형 가능

            int w = total / h;                 // 가로 후보

            if (w < h) continue;               // w >= h 조건 유지

            // 내부 영역이 center인지 확인 (테두리 1칸 제거)
            if ((w - 2) * (h - 2) == center) {
                return new int[]{w, h};
            }
        }

        // 문제 조건상 항상 정답이 존재하므로 여기까지 오지 않음
        return new int[]{0, 0};
    }
}

---

시간 복잡도

• H를 3부터 √total까지 검사한다.
• 각 반복에서 하는 일은 나눗셈/곱셈/비교 같은 상수 시간(O(1)) 작업
• 따라서 시간 복잡도는, O(√(frame + center))

---

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42842

프로그래머스