[프로그래머스] - 카펫

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고

테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만,

전체 카펫의 크기는 기억하지 못했습니다.

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

제한사항

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

입출력 예

 

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

---

1차 시도..?

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = {};
        /* testcase
        brown -> b yellow -> y
        b 9, y 1 -> [3, 3]
        b 10, y 2 -> [4, 3]
        b 12, y 3 -> [5, 3]
        b 12, y 4 -> [4, 4]
        b 16, y 5 -> [7, 3]
        b 14, y 6 -> [5, 4]
        
        규칙성?
        horizontal = if y % 2 == 0 -> (y / 2) + 2 else y + 2
        세로는 가로를 먼저 기준으로 하기 때문에 그 다음에 구하는게 맞는거 같음
        vertical = 음.. ?
        -> horizontal 24일경우 위 공식 아님 
        b 16, y 9 -> [5, 5]
        7같은 소인수는 가로 = 7 + 2 세로 -> 1 + 2 [9, 3]이 될것
        핵심 방법은 소수면 ho = Y + 2 ver = 1 + 2 에라토스테네스의 체?
        else 24일 경우 6 * 4라는 얘기
        30분 초과 외부 자료 도움
        구글링 시작
        소인수분해 -> 24 => 2 * 2 * 2 * 3
        72 -> 2 * 2 * 2 * 3 * 3 -> 가로 세로 구분을 어떻게 지어야 하나 [11, 10]이겠지만
        
        */
        
        return answer;
    }
}

시간 초과로 질문에서 답안

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];  // 결과 배열 생성
        
        if(yellow <= 2)
        {
            answer[0] = yellow + 2;
            answer[1] = 3;
            return answer;
        }
        
        int limit = (int)Math.ceil(Math.sqrt(yellow)); //제곱근 반올림하여 최대치

        for(int i=1; i<=limit ; ++i)
        {
            if(yellow % i == 0) { // 약수 구하기
                answer[0] = yellow/i; 
                answer[1] = i;
            } else 
                continue;

            if(answer[0]*2 + answer[1]*2 +4 == brown) 
            {
                answer[0] += 2;
                answer[1] += 2;
                return answer;
            }
        }

        // 소수 일 경우 
        answer[0] = yellow + 2;
        answer[1] = 3;

        return answer;
    }
}

// 이분꺼 참조-> https://programmers.co.kr/questions/13936

에라토스테네스로 소수 거른 다음에 먼저 리턴 시키고 소수 아닌 친구들 따로 돌리면 좀 더 빨라질 것 같은데... 일단 다른거 하러 떠나겠습니다

---

링크:

 

programmers.co.kr/learn/courses/30/lessons/42842

코딩테스트 연습 - 카펫