[완전탐색] 카펫

 

 

출처: 프로그래머스

 

문제 설명

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]

 

풀이과정

주어진 갈색과 노란색 타일 갯수 합을 구하고 중간에 약수만 찾아서 리턴해주면 답인줄 알았으나 

제출 시 다른 테스트 케이스 실패 에러

 

---

처음에 작성한 코드

import java.util.*;

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        ArrayList<Integer> arrList = new ArrayList<>();
        int sum = brown + yellow;
        int half = 0;
        
        for(int i = 1; i <= sum;i++ ){
            if(sum %i == 0){
                arrList.add(i);   
            }
        }// for 모든 사각형의 수 구하기
        
        half = arrList.size()/2;
        
        if(arrList.size()%2==0){
            answer[0]=arrList.get(half);
            answer[1]=arrList.get(half-1);
        }
        else{
            answer[0]=arrList.get(half);
            answer[1]=arrList.get(half);
        }
         
        return answer;
    }
}

 

수정 코드

import java.util.*;

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        int sum = brown + yellow;
        // 세로 a 가로 b
        int a, b = 0;
        // 세로가 더 짧음
        
        // (갈색타일 갯수 +4)/2 = 전체 가로 + 전체 세로
        
        for(a=1; a<=sum; a++){
            // 1.합의 약수 이면 일단 a가 세로길이 일 수 있음
            if(sum % a == 0 ){
                // 2. a를 이용하여 규칙에 따라 가로길이 구하고
                b = (brown+4)/2 - a;
                // 3. 구한 a,b(세로,가로)로 곱셈합(전체격자갯수)까지 체크되면 이것이 정답 
                if(brown + yellow == a*b){
                    answer[0] = a;
                    answer[1] = b;
                }
            }
        }

        return answer;
    }
}

 

 

note

return answer 값
2 * (전체 가로 + 전체 세로) -4 = 갈색 타일 갯수

그러면,
(갈색타일 갯수 +4)/2 = 전체 가로 + 전체 세로
->약수 전부 구해서 약수 가운데 값 두개 혹은 하나(약수 갯수가 홀수개일때)가 정답

->전체 가로, 전체 세로인 약수 가운데 2개만 구하여 answer에 등록하면 됨

 

전체 가로와 세로는 격자 합의 약수는 맞으나

갈색 타일 구하는 과정이 규칙에 따라 구하지 않아서 테스트 케이스 에러난듯...

 

// 1. 합의 약수 이면 일단 a가 세로길이 일 수 있음

// 2. a를 이용하여 규칙에 따라 가로길이 구하고

// 3. 구한 a,b(세로,가로)로 곱셈합(전체격자갯수)까지 체크되면 이것이 정답