[프로그래머스] (Java) 카펫 (완전탐색)

 

📑 1. 문제설명

---

💡 2. 접근방식

일단 숫자 사이의 규칙을 찾아주었다. 
 

노트에 해서 좀 지저분한데
brown + yellow를 해 준 뒤 그 숫자의 약수를 모두 찾아낸다. 약수들의 중간값이 찾고자 하는 숫자이다.
대신, 입출력 예를 보면 더 큰 숫자가 가로이고 더 짧은 숫자가 세로다.
 

brown	yellow	return
10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

 
여기서 brown + yellow 해 주면 각각
10+2 = 12
8 + 1 = 9
24 + 24 = 48
 
12의 약수 [1, 2, 3, 4, 6, 12]
9의 약수 [1, 3, 9] 
48의 약수 [1, 2, 3, 4, 6, 8, 12, 16, 24, 48] 중 정답은
 
약수의 갯수가 짝수면 가운데 있는 숫자 두 개 이다. (출력은 큰 숫자 먼저 해야 함)
약수의 갯수가 홀수면 가운데 숫자를 두 번 반복 해 준다.
 
그럼 약수가 담긴 ArrayList를 divisor이라고 하면 해당 숫자를 가져오기 위한 인덱스는
약수의 갯수가 짝수의 경우 divisor.size()/2, divisor.size()/2-1
홀수의 경우 divisor.size()/2 두 번이다.
 

---

⭐ 3. 내 코드

첫번째 시도 틀림
틀린 이유 : 약수 중 큰거 먼저 출력해야 하는데 작은거부터 순서대로 출력하다 보니 배열 내에서 두 숫자의 자리가 바뀌어 출력됨

 
위 에러에 따라 수정 해 준 코드(정답 아님)

import java.util.ArrayList;

class Solution {
    public int[] solution(int brown, int yellow) {
        int pl = brown + yellow; // brown과 yellow의 합을 구함
        ArrayList<Integer> divisor = new ArrayList<>();
        ArrayList<Integer> answer = new ArrayList<>();
        
        // mul의 약수를 찾아 divisor 리스트에 추가
        for (int i = 1; i <= mul; i++) {
            if (pl % i == 0) {
                divisor.add(i);
            }
        }

        int index1 = 0;
        int index2 = 0;
        
        // 약수가 짝수 개수일 경우
        if (divisor.size() % 2 == 0) {
            index1 = divisor.size() / 2;
            index2 = divisor.size() / 2 - 1;
            answer.add(divisor.get(index1));
            answer.add(divisor.get(index2));
        } else {
            // 약수가 홀수 개수일 경우
            index1 = divisor.size() / 2;
            index2 = divisor.size() / 2;
            answer.add(divisor.get(index1));
            answer.add(divisor.get(index2));
        }
        
        // ArrayList<Integer>를 int[]로 변환
        int[] intArray = answer.stream().mapToInt(Integer::intValue).toArray();
        
        return intArray;  
    }
}

두번째 시도 또틀림

정확성 76.9로
오답처리 되었다.
 

오답정리

왜 76점짜리 코드인가

1. 짝수/홀수 조건 사용 부정확
divisor.size()를 기준으로 짝수/홀수를 나누어 처리하지만, 문제의 조건에서 가로와 세로 길이를 직접 비교하는 논리가 없음.
실제 문제는 약수를 단순히 가져오는 것이 아니라, 약수 쌍 중 조건을 만족하는 가로와 세로를 찾는 작업을 해 줘야 함. 

2. 문제의 조건을 반영하지 않음
brown과 yellow의 배치를 고려한 식이 없기 때문.
예를 들어, (가로 - 2) * (세로 - 2) = yellow 조건을 만족해야 한다.

(가로 - 2) * (세로 - 2) = yellow 조건을 고려해야 하는 이유는 문제의 구조적 조건 때문이라고 한다. 문제의 요구사항은 단순히 직사각형의 넓이를 계산하는 것이 아니기 때문이다. 내부와 테두리의 구성을 만족하는 가로와 세로를 찾아야 한다. `(가로 - 2) * (세로 - 2) = yellow`는 이 요구사항을 만족하는지 확인하기 위한 핵심 조건인 셈이다.

---

 

 
brown과 yellow의 배치

- `brown`은 직사각형의 테두리를 구성한다.
- `yellow`는 직사각형의 내부 영역을 채운다.
 = 즉, `yellow`는 테두리로 둘러싸인 내부 공간의 넓이이다.
 
예) brown = 10, yellow = 2인 경우, 직사각형의 배치

BBBB
BYYB
BBBB

 

문제의 조건

직사각형의 전체 넓이 = brown + yellow
직사각형 내부에서 (가로 - 2) * (세로 - 2)는 테두리를 제외한 yellow 부분의 넓이

 

계산
 

가로와 세로 길이가 width와 height일 때 전체 넓이 = width * height = brown + yellow
테두리를 제외한 내부 넓이가 Yellow와 같아야 한다. 
yellow = (width - 2) * (height - 2)
 

---

🐦 정답코드(완전탐색)

class Solution {
    public int[] solution(int brown, int yellow) {
        int area = brown + yellow; // 전체 넓이
        
        // 전체 넓이의 약수 탐색
        for (int height = 1; height <= Math.sqrt(area); height++) {
            if (area % height == 0) { // area(넓이)와 height(높이)가 정확히 나누어떨어지는지 확인
                int width = area / height; // 가로는 넓이를 높이로 나눈 값
                
                // 조건을 만족하는지 확인
                if ((width - 2) * (height - 2) == yellow) {
                    return new int[] { width, height }; // 가로 ≥ 세로 조건을 자동으로 만족
                }
            }
        }
        return new int[] {};
    }
}

 

약수 탐색을 할 때 제곱근까지만 탐색하는 이유?

약수는 대칭적인 특성을 가짐. 어떤 정수 N의 약수는 쌍(pair)으로 존재하기 때문.
예를 들어, N=36일 때 약수는 (1*36), (2*18), (3*12), (4*9), (6*6)
약수는 서로 곱해서 N이 되는 두 숫자들이기 때문에 제곱근을 기준으로 대칭적으로 나타난다는 것이다.
즉, 루트 36 = 6 이후에는 순서만 바뀐 (9*4), (12*3), (18*2), (36*1)이 반복되기 때문에 더 이상 탐색할 필요가 없다.

---

👏🏻좋아요 제일 많이 받은 코드

근의 공식으로 풀다니

import java.util.*;
class Solution {
    public int[] solution(int brown, int red) {
        int a = (brown+4)/2;
        int b = red+2*a-4;
        int[] answer = {(int)(a+Math.sqrt(a*a-4*b))/2,(int)(a-Math.sqrt(a*a-4*b))/2};
        return answer;
    }
}

 

class Solution {
    public int[] solution(int brown, int red) {
        for(int i=1; i<=red; i++) {
            if(red%i==0 && (red/i+i)*2+4==brown) {
                return new int[] {red/i+2, i+2};
            }
        }
        return null;
    }
}

 

---

👉🏻 4. 같은 유형 문제 (완전탐색)