처음에 봤을 때,
문제를 이해하는데는 그렇게 어렵지 않았다.
그냥 약수 구해서 두 값 더해서 *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 문제풀이
나의 코드 시간 복잡도: O(sqrt(N)) or O(N) # 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 if N == 1: return..
datacodingschool.tistory.com
그리고 그 결과 같은 방법으로 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문제씩 공부해야겠다.
'Codility' 카테고리의 다른 글
| Codility - CountNonDivisible 문제풀이 - Henry's Algorithm (0) | 2020.10.02 |
|---|---|
| Codility - Peaks 문제 풀이 - Henry's Algorithm (2) | 2020.09.08 |
| Codility - Flags 문제풀이 (0) | 2020.07.03 |
| Codility - CountFactors 문제풀이 (0) | 2020.06.23 |
| Codility - MaxSliceSum 문제풀이 (0) | 2020.05.21 |
