Codility Lesson 10 - MinPerimeterRectangle(JAVA)

https://app.codility.com/programmers/lessons/10-prime_and_composite_numbers/min_perimeter_rectangle/

MinPerimeterRectangle coding task - Learn to Code - Codility

 

문제

- 정수 N이 주어지며, 사각형의 영역을 의미한다.

- 사각형의 영역의 A, B는 각 선을 의미하며 N = A * B를 만족하고, perimeter는 2 * ( A + B )이다.

- 같은 영역의 N의 영역에서 perimeter의 최소값을 구하는 것이 목표이다.

- 예시 : N= 30, 사각형의 영역은 30일 때,

• (1, 30), with a perimeter of 62,
• (2, 15), with a perimeter of 34,
• (3, 10), with a perimeter of 26,
• (5, 6), with a perimeter of 22.

예시에서 22가 최소값으로 return 22를 한다.

 

제한조건

• N is an integer within the range [1..1,000,000,000].

N은 1 ~ 1,000,000,000사이의 정수이다.

 

풀이

- 앞전에 풀었던 약수를 구하는 문제를 활용한다.( 약수는 제곱근을 넘지 않는 것을 활용하는 것 )

- 약수를 구하고, 약수인 경우에는 perimeter를 구하고 최소값을 초기화해서 비교하여 최소값을 찾아낸다.

 

예상 시간복잡도 : O(sqrt(N))

 

소스코드

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int N) {
        // write your code in Java SE 8
        if( N == 1 ) return 1;

        double sqrtN = Math.sqrt(N);
        int limit =(int)sqrtN;

        int minVal = Integer.MAX_VALUE;
        int perimeter = 0;
        for( int i = 1; i < limit+1; i++ ){
            if( N % i == 0 ){
                int mok = N / i;
                perimeter = 2 * (mok + i);
                minVal = Math.min(perimeter, minVal);
            }
        }

        return minVal;
    }
}

 

- N이 1일 때 return값은 1이 아니라, 2 * ( 1 + 1 ) = 4인 부분을 놓쳤다...

- N == 1일 때를 굳이 예외처리로 안넣어도 아래식에서 해결될 것..

 

재풀이 소스코드

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int N) {
        // write your code in Java SE 8

        double sqrtN = Math.sqrt(N);
        int limit =(int)sqrtN;

        int minVal = Integer.MAX_VALUE;
        int perimeter = 0;
        for( int i = 1; i < limit+1; i++ ){
            if( N % i == 0 ){
                int mok = N / i;
                perimeter = 2 * (mok + i);
                minVal = Math.min(perimeter, minVal);
            }
        }

        return minVal;
    }
}