-
소수 만들기 (프로그래머스, 레벨1)개발자의 길/Algorithm 2021. 3. 27. 19:54
https://programmers.co.kr/learn/courses/30/lessons/12977
처음 아이디어는 조합을 이용하는 것이다. 모든 경우를 다 구해서 각각 확인한다.
파이썬은 combinations()를 제공하므로 어렵지 않다. 다른 사람도 대부분 그렇게 푼 것 같다.
다른 방법이 없을까 고민해봤다.
예전에 수학 문제를 풀 때 생각했던 게 기억나서 다음과 같이 아이디어를 생각해냈다.
1. 여러 개의 수를 더할 때 홀수가 짝수 개 포함되어 있으면 합은 짝수이다.
2. 짝수는 소수가 아니다.따라서, 다음과 같은 구조로 코드를 작성했다.
1. 소수 판별 부분
2. 리스트에서 홀수 개수 구하기. 홀수가 0개면 모든 부분합이 짝수이므로 소수는 없다. 0을 리턴.
3. 서로 다른 3개의 원소만 가져와서 합을 구하므로, 소수가 될 수도 있는 경우는 두 가지다.
3-1. 홀수 1개, 짝수 2개
3-2. 홀수만 3개구현한 코드는 아래와 같다.
1234567891011121314151617181920212223242526272829303132333435363738394041424344import mathdef solution(nums):# 소수 판별def is_prime(x):for i in range(2, int(math.sqrt(x) + 1)):if x % i == 0:return Falsereturn True# 홀수 개수 확인 및 홀수, 짝수 구분count = 0odd_num = []even_num = []for i in nums:if i % 2:odd_num.append(i)count += 1else:even_num.append(i)# nums의 모든 숫자가 짝수면, 숫자 3개 합이 소수가 될 수 없다.if count == 0: return 0# 3개 원소 합 구하기temp = []for i in odd_num: # 홀수 1개, 짝수 2개인 경우for j in range(len(even_num) - 1):for k in range(j + 1, len(even_num)):temp.append(i + even_num[j] + even_num[k])if count > 2: # 홀수 3개인 경우for i in range(len(odd_num) - 2):for j in range(i + 1, len(odd_num) - 1):for k in range(j + 1, len(odd_num)):temp.append(odd_num[i] + odd_num[j] + odd_num[k])# 3개 원소 합 중 소수 개수 구하기answer = 0for i in temp:if is_prime(i) == True:answer += 1return answercs 조합을 이용한 풀이도 작성해서 비교해 보았더니, 경우의 수를 줄이기 때문에 위 방식이 조금 더 빠르다.
극단적으로 'nums'에 짝수가 대부분이고 홀수는 0개, 1개, 3개 같은 경우라면 더 차이가 날 것이다.
'개발자의 길 > Algorithm' 카테고리의 다른 글
프로그래머스 연습문제 레벨1 클리어 (0) 2021.03.30 약수의 개수, 약수의 합 공식 (0) 2021.03.27 약수의 합 (프로그래머스, 레벨1), 양의 약수의 합 공식 (0) 2021.03.17 큰 수 만들기 (프로그래머스, 레벨2) (0) 2021.03.12 무엇이 추구해야 할 방향인가? (0) 2021.03.10