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

📘 연습 문제  : 전시판 테두리 만들기

 

문제 설명

한 전시장에 직사각형 전시판을 설치하려고 합니다.

• 전시판의 테두리(두께 1칸)는 border개의 칸으로 이루어져 있습니다.
• 전시판의 중앙 영역(테두리를 제외한 내부)은 inner개의 칸으로 이루어져 있습니다.
• 전시판의 가로 길이를 W, 세로 길이를 H라고 할 때 다음 조건을 만족해야 합니다.
  • W ≥ H
  • W ≥ 3, H ≥ 3

border와 inner가 주어질 때, 전시판의 [가로 길이, 세로 길이]를 구하세요.
정답은 항상 하나만 존재합니다.

---

입력

• border : 테두리 칸의 개수 (정수)
• inner : 내부 칸의 개수 (정수)

---

출력

• 전시판의 [가로, 세로] 길이를 담은 배열

---

예시

💡입력

border = 18
inner = 6

 

💡설명

• 전체 칸 수 = 24
• 가능한 (W, H) 중
  • (6, 4) → (6-2) × (4-2) = 8 ❌
  • (8, 3) → (8-2) × (3-2) = 6 ⭕
• 결과: [8, 3]

---

Algorithm

1. 전체 칸 수 total = border + inner를 계산한다.
2. 전시판은 직사각형이므로, H(세로)를 후보로 잡고 약수 탐색을 한다.
   • H는 최소 3부터 시작한다.
3. total % H == 0이면 W = total / H로 가로 후보를 계산한다.
4. W ≥ H 조건을 만족할 때만 진행한다.
5. 내부 영역 크기가 조건을 만족하는지 확인한다.
   • 테두리 두께가 1칸이므로 내부는 (W - 2) × (H - 2)
   • 이것이 inner와 같으면 [W, H]가 정답이다.
6. 정답을 반환한다. (문제 조건상 정답은 1개)

---

Code

class Solution {
    public int[] solution(int border, int inner) {
        int total = border + inner;

        // 세로(H) 후보를 3부터 √total 까지 탐색
        for (int h = 3; h * h <= total; h++) {
            // 직사각형이 되려면 total이 h로 나누어떨어져야 함
            if (total % h != 0) continue;

            int w = total / h;     // 가로(W) 후보

            // 문제 조건: 가로 >= 세로
            if (w < h) continue;

            // 내부 칸 수가 inner인지 확인
            if ((w - 2) * (h - 2) == inner) {
                return new int[]{w, h};
            }
        }

        // 문제 조건상 정답은 항상 존재
        return new int[]{0, 0};
    }
}

---

시간 복잡도

• H를 3부터 √total까지 검사하면 충분 (약수는 대칭이므로)
• 각 반복에서 수행하는 작업은 나눗셈/곱셈/비교 정도로 상수 시간(O(1))

✅ 따라서 시간 복잡도는

• O(√(border + inner))

---

문제 링크

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

프로그래머스