MinPerimeterRectangle (Codility) - Java

문제

사각형의 넓이 N이 주어진다. 이 넓이를 만족하는 사각형의 가로, 세로 길이 A, B 길이에서 2 * (A + B)의 값을 perimeter라고 한다. 이 perimeter중 가장 최솟값을 반환하라.

 

만약 N이 30인 경우 이를 만족하는 사각형의 길이 A, B는 (1, 30), (2, 15), (3, 10), (5, 6)가 있다. 이 중 perimeter가 가장 작은 값음 (5, 6)으로 2 * (5 + 6) = 22이다.  

 

해결 방법

1부터 N까지 N을 나눌때 나누어지는 경우는 넓이를 만족하는 A, B를 구해놓는다. 이 중 perimeter가 가장 최소인 값을 구하면 된다. 하지만 이렇게 하는 경우 O(N) 시간복잡도로 타임아웃이 될것이다. 그러면 제한시간을 만족하는 방법은 무엇이 있을까?

 

1 ~ N까지 구하는 경우 중간지점을 넘어가면 이전에 구해놨던 A, B와 중복이 된다. 예를들어 N이 30인 경우 다음과 같은 중복이 있다.

 

N = 30

(1, 30)
(2, 15)
(3, 10)
(5, 6)
---- 이 밑으로는 위와 중복된다. -----> 중간 지점
(6, 5)
(10, 3)
(15, 2)
(30, 1)

중복되는 시점은 √N 시점부터 이므로 이 값을 넘지 않는 범위에서 A, B를 구해주면 된다.

 

구현 코드는 다음과 같다.

import java.lang.Math;

class Solution
{
	public int solution(int N) 
	{
		int min = (N + 1) * 2;

		for(int i = 1; i <= Math.sqrt(N); ++i)
		{
			if(N % i == 0)
			{
				int result = (i + (N / i)) * 2;
				if(min > result) min = result;
			}
		}

		return min;
	}
}