[Programmers] Lv2_카펫 (JAVA)

💻JAVA 코드 바로보기



□문제 설명

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]

 

 

---

🌼 JAVA 알고리즘

 

 

□초기화면

 

 

 

 

 

 

 

 

□풀이과정

문제를 풀기 전에, 문제유형인 '완전탐색'에 대해 알아보자. 완전탐색이란? 가능한 모든 경우의 수를 체크하여 답을 도출하는 방법 예를 들어 비밀번호를 찾는다고 했을 때, 0부터 9999까지 모든 수를 체크하면서 찾는 방법이다. 이번 문제는 yellow의 개수로 만들 수 있는 모든 사각형의 크기를 구하고, yellow의 너비+brown의 양옆개수(2) 와 yellow의 높이+brown의 상하개수(2)를 곱한 값이 yellow+brown의 개수와 동일한 경우를 완전탐색으로 찾으면 해결되는 간단한 문제이다.

1. yellow로 만들 수 있는 사각형의 경우의 수를 구한다. 2. 최종 사각형의 넓이 - yellow사각형의 넓이 == brown의 넓이 를 체크한다.

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        
        //완전탐색 : 모든 경우의 수를 찾는 풀이법
        
        //yellow가 만들어지는 경우의 수
        for(int i=1;;i++)
            for(int j=1;;j++)
                if(i*j==yellow) {
                    //brown 개수 체크
                    if((i+2)*(j+2)-yellow==brown){
                        answer[0] = j+2;
                        answer[1] = i+2;
                        return answer;
                    }
                }
    }
}

테스트케이스1과 2와 같이 yellow의 높이가 1인 비교적 간단한 케이스는 쉽게 통과했지만, yellow의 높이가 4인 경우가 시간초과가 나왔다. for문의 상태를 체크해보고자 출력문 추가했다.

	for(int i=1;;i++)
            for(int j=1;;j++)
                if(i*j==yellow) {
                    System.out.println("yellow -> "+i+" "+j);		//출력문 추가
                    //brown 개수 체크
                    if((i+2)*(j+2)-yellow==brown){
                        answer[0] = j+2;
                        answer[1] = i+2;
                        return answer;
                    }
                        
                }

큰실수를 하고있었다! 두번째 for문의 조건문이 없어 i는 계속해서 1인 상태로 머물고 있는 상태였다.

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        
        //완전탐색 : 모든 경우의 수를 찾는 풀이법
        
        //yellow가 만들어지는 경우의 수
        for(int i=1;;i++)
            for(int j=1;j*i<=yellow;j++)
                if(i*j==yellow) {
                    System.out.println("yellow -> "+i+" "+j);
                    //brown 개수 체크
                    if((i+2)*(j+2)-yellow==brown){
                        answer[0] = j+2;
                        answer[1] = i+2;
                        return answer;
                    }
                        
                }
    }
}

i와 j의 곱이 yellow와 brown의 총합보다 높아지지 않도록 조건문을 추가하여 해결했다.

 

 

 

 

 

 

 

 

 

□완성 코드

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        
        //yellow가 만들어지는 경우의 수
        for(int i=1;;i++)
            for(int j=1;j*i<=yellow;j++)
                if(i*j==yellow) {
                    //brown 개수 체크
                    if((i+2)*(j+2)-yellow==brown){
                        answer[0] = j+2;
                        answer[1] = i+2;
                        return answer;
                    }
                        
                }
    }
}

 

 

 

 

 

 

 

---

□링크

About Me

코딩테스트 연습 - 카펫