https://app.codility.com/programmers/lessons/10-prime_and_composite_numbers/min_perimeter_rectangle/
문제
- 정수 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;
}
}
'코딜리티 문제풀이' 카테고리의 다른 글
Codility Lesson 10 - Peaks(JAVA) (0) | 2022.04.29 |
---|---|
Codility Lesson 10 - Flags(JAVA) (0) | 2022.04.19 |
Codility Lesson 10 - CountFactors(JAVA) (0) | 2022.04.08 |
Codility Lesson 09 - MaxDoubleSliceSum(JAVA) (0) | 2022.04.04 |
Codility Lesson 09 - MaxSliceSum(JAVA) (0) | 2022.04.03 |