[Programmers/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]

출처

※ 공지 - 2020년 2월 3일 테스트케이스가 추가되었습니다.

※ 공지 - 2020년 5월 11일 웹접근성을 고려하여 빨간색을 노란색으로 수정하였습니다.

 

풀이 1(실패)

i와 j가 주어질때 brown과 yellow를 구하는 방법은 생각이 났으나, 그 반대는 생각나지 않아 이중for문으로 찾았다.

완전탐색이므로, 반복문을 이용해야겠다는 생각이 바로 들었다. 

작성코드 1(실패)

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        //4, 3 일때 brown&yellow 계산법 -> 4*2+(3-2)*2 = brown , (4-2)*(3-2)=yellow
        int max = Math.max(brown, yellow);
        for(int i=0;i<max;i++){
            for(int j=0;j<max;j++){
                if(i*j==(brown+yellow)&&((i*2+(j-2)*2)==brown)&&((i-2)*(j-2)==yellow)){
                    answer[0]=i;
                    answer[1]=j;
                    break;
                }
            }
        }
        return answer;
    }
}

역시 2중for문은 바로 시간초과 가 떠버렸다.

 

 

풀이 2(성공)

for문을 전부 다 돌리는 것은 비효율적이다. 

일단 가로길이는 brown/2 의 값보다 무조건 작기 때문에, (column이 3이상이어야 yellow가 존재해서 brown길이/2 보다 가로는 짧을 수 밖에 없다. brown/2가 가로길이가 되면 yellow는 존재할 수 없음.)

세로 길이는 가로길이에 영향을 받지만, 일단 넓이의제곱근/2 보다는 크고, 넓이의 제곱근 값보다 작거나 같다.

이를 이용해서 코드를 작성하였다. 

작성코드 2(성공)

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        //넓이가 brown+yellow인 점을 활용
        int area = brown+yellow;
        int root = (int) Math.ceil(Math.sqrt(area));
        //가로길이는 brown/2보다 무조건 작고 세로길이의 합은 root*2 보다작음
        for(int row=1;row<brown/2;row++){
            for(int column=(root-1)*2-row;column<=root*2;column++){
                if(row*column==area&&(row-2)*(column-2)==yellow&&(row*2+(column-2)*2)==brown){
                   // System.out.println("brown : "+brown+", yellow : "+yellow);
                    answer[0]=row;
                    answer[1]=column;
                    break;
                }
            }
        }
        //System.out.println(answer[0]+", "+answer[1]);
        return answer;
    }
}

 

+ 검색을 해 보니 약수를 이용해서 통과한 경우가 꽤 있다. 

약수를 왜 생각을 못했을까..

깔끔한 코드는 아닌 것 같다.