[알고리즘] 프로그래머스 카펫 (레벨 2) / 자바 java 풀이

프로그래머스 완전탐색 문제 중 하나인 카펫 문제이다.

 

이 문제는 직사각형의 크기 (가로 *세로) 구하는 식만 생각해 내면 어렵지 않게 해결이 가능한 문제였다.

 

📑 카펫

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

문제 설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해 주세요.

---

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

---

입출력 예

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

 

 

✏️ 문제 해결 방법

노란색의 타일이 적어도 하나 이상 들어가기 위해서는 가로, 세로 길이가 적어도 3 이상이어야 한다. 그리고 이 카펫의 크기는 가로가 세로보다 크거나 같다. 

1. 전체 카펫의 크기 

brown과 yellow 각각의 개수를 기억하기 때문에 brown + yellow는 전체 격자의 개수가 된다. 즉, 전체 격자의 개수는 전체 카펫의 크기가 된다.

// 전체 격자의 개수 = 카펫의 크기
int n = brown + yellow;

 

2. 직사각형의 크기 (가로 * 세로)

직사각형의 크기는 가로 * 세로의 곱으로 구해진다. ①현재 주어진 사각형에서 한 변의 길이는 3 이상으로 조건이 주어지고 있으며 ②가로길이는 세로 길이보다 크거나 같다 는 조건이 주어져있다. (※ 여기서 가로와 세로의 모든 조건을 하나씩 구해보는 과정을 거치기에 완전탐색이 된다.)

 

한 변의 길이는 최소 3 이기 때문에 반복문의 시작은 3으로 시작한다. 한 쌍의 약수는 서로 대칭이 되기 때문에 제곱근까지만 반복하면 된다. 효율성 측면에서도 좋지만 이 문제에서는 작은 값과 큰 값을 쉽게 구분할 수 있어 변수는 세로, 변수와 나누어 나오는 값은 가로로 쉽게 구할 수 있다.

for(int i = 3 ; i <= Math.sqrt(n) ; i++) {
    if(n % i == 0) {
		y = n / i;
	}
}

여기서 가로, 세로 길이가 나온다고 모두 답이 될 수 없다. 문제의 조건과 동일한지 확인해주어야 한다. 

 

 

3. 노란색 카펫 크기 확인

갈색 카펫은 테두리 한 줄로 칠해져 있으며 나머지는 노란색 카펫이다. 그렇다면 노란색 카펫은 (x-2) * (y-2)가 될 것이다. 

for(int i = 3 ; i <= Math.sqrt(n) ; i++) {
	if(n % i == 0) {
		y = n / i;
        	// ✨ 추가된 코드
		if((i-2)*(y-2)== yellow) {
			return new int[]{y, i};
		}
	}
}

 

노란색 격자를 확인하는 코드를 추가해 준다.

 

위의 코드를 모두 합치면 다음과 같다.

 

 

전체 코드

class Solution {
    public int[] solution(int brown, int yellow) {
        
        int n = brown + yellow;
        
        int y;
        
        for(int i = 3 ; i <= Math.sqrt(n) ; i++) {
            if(n % i == 0) {
                y = n / i;
                
                if((i-2)*(y-2)== yellow) {
                    return new int[]{y, i};
                }
            }
        }
        
        return new int[]{0,0};
    }
}

 

🕸️ 문제 풀이 소감

문제를 풀어놓고 며칠 지나 스터디를 하니 n=3 이렇게 해놓고 왜 3부터 시작했는지 나도 까먹어 버려서 당황했다. 별 거 아니었는데.. ㅎㅎ 이렇게 바로바로 정리를 하는 습관을 길러야겠다. 

 

---

궁금한 점이 있거나 잘못된 부분이 있다면 얼마든지 댓글로 남겨주세요 🤗

감사합니다!

 

"이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다."