출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/12923
더보기
먼저, 생각해야 할 부분
1. 조건이 상당히 많다.
패턴을 찾는 것도 중요하지만 조건을 따로 기록하며 빼먹지 않도록 주의하자.
2. 효율성 테스트가 실패가 뜬다면, 1번을 마음에 새기자............
풀이
#자기자신을 제외한 가장 큰 약수
def maxYaksuExceptMe(number):
if number == 1:
return 0
for i in range(2, int(number**0.5)+1):
if number % i == 0 and number // i <= 10000000:
return number // i
return 1
def solution(begin, end):
answer = []
for num in range(begin, end+1):
answer.append(maxYaksuExceptMe(num))
return answer
모든 숫자는 자기 자신을 제외하고 자기 자신의 배수들에 적히게된다.
숫자는 계속 덮어 씌워질 것이기 때문에 최종적으로는 자기 자신을 제외하고 가장 큰 약수가 적히게 된다.
즉, 1을 제외하고는 약수를 효율적으로 찾아서 자기자신을 빼고 가장 큰 약수를 return하면 된다.
정확도 테스트는 전부 맞는데 효율성 테스트에서 실패가 떴다면,
10,000,000번째 블록까지만 사용했다는 조건을 간과한 것이다.
10,000,000번째 블록까지만 사용했으므로, 적힐 수 있는 가장 큰 수가 10,000,000까지이다.
즉, 약수를 구하는 과정에서 10,000,000보다 큰 약수는 블록에 적힐 수 없다.
시간 복잡도
-
알게 된 점
-
고찰
-
Github
'알고리즘 > Python' 카테고리의 다른 글
[python] 프로그래머스 - 성격 유형 검사하기 (0) | 2023.03.09 |
---|---|
[python] 프로그래머스 - 최솟값 만들기 (0) | 2022.07.17 |
[python] 프로그래머스 - 3 x n 타일링 (0) | 2022.07.14 |
[python] LeetCode #1 - Two Sum (0) | 2022.07.13 |
[python] 백준 14430 - 자원 캐기 (0) | 2022.07.10 |