알고리즘

[프로그래머스/JAVA] 카펫

데메즈 2022. 2. 7. 22:59
728x90
반응형

https://programmers.co.kr/learn/courses/30/lessons/42842?language=java

 

코딩테스트 연습 - 카펫

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

programmers.co.kr

 

import java.util.*;
class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        int total;
        
        total = brown + yellow;
        
        for(int i=3; i<=Math.sqrt(total); i++){
            if(total%i==0 && 2*(i+(total/i))-4 == brown){
                answer[0]=total/i;
                answer[1]=i;
            }
        }
        
        return answer;
    }
}

 

푼 방법은 일단 갈색이랑 노랑색의 개수를 더하고

두 수를 곱해서 그 수가 나오는지 확인하는 방법으로 접근했다.

 

갈색이 8이상, 노랑이 1 이상이기 때문에 가로, 세로 길이는 3이상이 된다.

 

곱은 1*2 = 2*1 처럼 반대로도 되기때문에 시간을 줄이기 위해  for 문은  total의 제곱근까지만 돌린다.

 

처음에는 통과를 못했는데 그 이유가

2*(i+(total/i))-4 == brown

이 조건을 넣지 않았기 때문이다.

 

이 조건은 2*6 = 3*4 와 같은 경우 때문에 필요하다.

 

그리고 가로가 길기 때문에 total/i 를 먼저, i 를 나중에 answer 에 넣어주면 된다.

728x90
반응형