Codility - MinPerimeterRectangle 문제풀이

 

 

 

처음에 봤을 때,

문제를 이해하는데는 그렇게 어렵지 않았다.

 

그냥 약수 구해서 두 값 더해서 *2 해주면 되는데,

그 중 최소값을 찾는 문제구나 라는 생각만 하였고 접근했다.

 

첫 시도했을 때는 아래의 코드와 같다.

그런데 80%의 정확도만 나왔다.

 

그 원인을 살펴보니 큰 수에 대해서는 for문에서 i 가 일일히 +1씩 되면서 진행되는 부분이

성능이 좋지 않음을 알 수 있었다.(Timeout Error 발생ㅜㅜ)

 

그래서 for i in range(2,int(i/2)): 처럼 나누기 2를 해보기도 하고 그랬는데,

역시나 마찬가지였다.

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(N):
    # write your code in Python 3.6
    
    check = N
    max_perimeter = 2*(1+(N))
    
    for i in range(1,N+1):
        
        # 반복되는 값이 가장 최근의 몫의 값보다 커지면 그만
        if i >= check:
            break
        
        # 0으로 나눠지면 약수
        if N%i == 0:
            max_perimeter = min(max_perimeter,2*(i+(N/i)))
            check = N/i
    
    return int(max_perimeter)
    
    pass

 

잠깐 들었던 생각이

이전에 풀었던 Codility 문제 중에 CounterFactors라는 문제에서도 약수를 구하는 문제였는데,

조금 다르게 접근했던 것 같은 기억이 있어서 찾아보았다.

https://datacodingschool.tistory.com/69

Codility - CountFactors 문제풀이

 

 

그리고 그 결과 같은 방법으로 For 문을 돌리고 100% 정확도를 얻을 수 있었다.

 

약수를 구하는 문제에는 이제 i*i 라는 방식을 사용해주어야겠다.

 

 

두번째 시도했을 때 코드

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(N):
    # write your code in Python 3.6
    
    max_perimeter = 2*(1+(N))
    number_iter = 1
    
    while number_iter*number_iter < N:
        # 약수이면
        if N/number_iter%1 == 0:
            max_perimeter = min(max_perimeter,2*(number_iter+(N/number_iter)))
            
        number_iter += 1
        
    if number_iter*number_iter == N:
        max_perimeter = min(max_perimeter,4*number_iter)
    
    return int(max_perimeter)
    
    pass
   

 

 

 

이번주 토요일에 이베이 코딩테스트,

다음주 토요일에 LG U+ 코딩테스트가 있는데,

매일 꾸준히 3문제씩 공부해야겠다.