코딩 테스트/Level 2
41. 소수 만들기
컴닥
2020. 8. 24. 19:19
반응형
소수 만들기
Summer/Winter Coding(~2018)
2420명 완료
https://programmers.co.kr/learn/courses/30/lessons/12977
코딩테스트 연습 - 소수 만들기
주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 �
programmers.co.kr
파이썬
저는 itertools를 적극적으로 이용했습니다.
파이썬의 itertools.groupby는 판다스의 groupby 때문에 검색도 어렵습니다.
공식 문서를 참고하시면 됩니다.
https://docs.python.org/ko/3.8/library/itertools.html#itertools.groupby
from itertools import groupby
print([(k, list(g)) for k, g in groupby('AAAABBBCCDAABBB')])
# [('A', ['A', 'A', 'A', 'A']), ('B', ['B', 'B', 'B']), ('C', ['C', 'C']), ('D', ['D']), ('A', ['A', 'A']), ('B', ['B', 'B', 'B'])]
특정한 범위에서 소수를 여러 개 찾아야 하기 때문에
에라토스테네스의 채를 이용하는 게 효율적일 것 같습니다.
def solution(nums):
from itertools import combinations, groupby
sums = tuple((num, len(tuple(g))) for num, g in groupby(sorted(map(sum, combinations(nums, 3)))))
max_sum = sums[-1][0]
primes = [False, False] + [True] * (max_sum - 1)
for i in range(2, max_sum + 1):
if primes[i]:
for j in range(i * 2, max_sum + 1, i):
primes[j] = False
return sum(length for num, length in sums if primes[num])테스트 1 〉 통과 (0.69ms, 10.3MB)
테스트 2 〉 통과 (1.20ms, 10.2MB)
테스트 3 〉 통과 (0.28ms, 10.2MB)
테스트 4 〉 통과 (0.16ms, 10.3MB)
테스트 5 〉 통과 (0.86ms, 10.1MB)
테스트 6 〉 통과 (1.75ms, 10.6MB)
테스트 7 〉 통과 (0.36ms, 10.2MB)
테스트 8 〉 통과 (4.11ms, 10.5MB)
테스트 9 〉 통과 (0.58ms, 10.1MB)
테스트 10 〉 통과 (3.85ms, 10.6MB)
테스트 11 〉 통과 (0.09ms, 10.2MB)
테스트 12 〉 통과 (0.05ms, 10.2MB)
테스트 13 〉 통과 (0.07ms, 10.2MB)
테스트 14 〉 통과 (0.04ms, 10.1MB)
테스트 15 〉 통과 (0.04ms, 10.3MB)
테스트 16 〉 통과 (4.91ms, 10.9MB)
테스트 17 〉 통과 (5.39ms, 11MB)
테스트 18 〉 통과 (0.48ms, 10.2MB)
테스트 19 〉 통과 (0.47ms, 10.2MB)
테스트 20 〉 통과 (6.16ms, 11.1MB)
테스트 21 〉 통과 (5.60ms, 11MB)
테스트 22 〉 통과 (1.54ms, 10.4MB)
테스트 23 〉 통과 (0.01ms, 10.1MB)
테스트 24 〉 통과 (4.89ms, 11MB)
테스트 25 〉 통과 (5.00ms, 10.9MB)
테스트 26 〉 통과 (0.02ms, 10.1MB)
하지만 내장 함수를 안 쓰고 푸는 게 더 빠르네요.
def solution(nums):
sums = {}
max_sum = 0
answer = 0
for i in range(len(nums)-2):
for j in range(i + 1, len(nums) - 1):
for k in range(j + 1, len(nums)):
temp_sum = nums[i] + nums[j] + nums[k]
sums[temp_sum] = sums.get(temp_sum, 0) + 1
if temp_sum > max_sum:
max_sum = temp_sum
primes = [False, False] + [True] * (max_sum - 1)
for i in range(2, max_sum + 1):
if primes[i]:
if i in sums:
answer += sums[i]
for j in range(i * 2, max_sum + 1, i):
primes[j] = False
return answer테스트 1 〉 통과 (1.19ms, 10.1MB)
테스트 2 〉 통과 (0.88ms, 10.2MB)
테스트 3 〉 통과 (0.19ms, 10MB)
테스트 4 〉 통과 (0.16ms, 10.2MB)
테스트 5 〉 통과 (0.97ms, 10.2MB)
테스트 6 〉 통과 (1.62ms, 10.2MB)
테스트 7 〉 통과 (0.36ms, 10.2MB)
테스트 8 〉 통과 (3.42ms, 10.3MB)
테스트 9 〉 통과 (0.46ms, 10.1MB)
테스트 10 〉 통과 (3.28ms, 10.2MB)
테스트 11 〉 통과 (0.05ms, 10.1MB)
테스트 12 〉 통과 (0.04ms, 10.2MB)
테스트 13 〉 통과 (0.06ms, 10.2MB)
테스트 14 〉 통과 (0.04ms, 10.3MB)
테스트 15 〉 통과 (0.06ms, 10.1MB)
테스트 16 〉 통과 (4.06ms, 10.3MB)
테스트 17 〉 통과 (4.89ms, 10.3MB)
테스트 18 〉 통과 (0.50ms, 10.4MB)
테스트 19 〉 통과 (0.46ms, 10.3MB)
테스트 20 〉 통과 (5.75ms, 10.3MB)
테스트 21 〉 통과 (5.68ms, 10.4MB)
테스트 22 〉 통과 (1.37ms, 10.2MB)
테스트 23 〉 통과 (0.01ms, 10.3MB)
테스트 24 〉 통과 (5.29ms, 10.3MB)
테스트 25 〉 통과 (4.26ms, 10.4MB)
테스트 26 〉 통과 (0.01ms, 10.1MB)GO
습관적으로 파이썬 스타일로 문제를 풀게 되더군요..
하지만 곧 파이썬에서 사용하던 내장 함수들을 일일이 만들고 있는 저를 보며.. 깊은 반성이..
func sum(arr []int) (result int) {
for _, each := range arr {
result += each
}
return
}
func combinate(result *[][]int, arr []int, visited []bool, start int, n int, r int) {
if r == 0 {
var temp []int
for i, v := range visited {
if v == true {
temp = append(temp, arr[i])
}
}
*result = append(*result, temp)
return
}
for i := start; i < n; i++ {
visited[i] = true
combinate(result, arr, visited, i+1, n, r-1)
visited[i] = false
}
}
func solution(nums []int) (answer int) {
var result [][]int
var visited = make([]bool, len(nums))
combinate(&result, nums, visited, 0, len(nums), 3)
sums := make(map[int]int)
for _, each := range result {
sums[sum(each)]++
}
max := 0
for each := range sums {
if each > max {
max = each
}
}
primes := make([]bool, max+1, max+1)
primes[0], primes[1], primes[2] = false, false, true
for i := 2; i < max+1; i++ {
primes[i] = true
}
for i := 2; i < max+1; i++ {
if primes[i] {
if v, ok := sums[i]; ok {
answer += v
}
for j := i * 2; j < max+1; j += i {
primes[j] = false
}
}
}
return
}테스트 1 〉 통과 (1.12ms, 7.58MB)
테스트 2 〉 통과 (1.52ms, 7.84MB)
테스트 3 〉 통과 (0.33ms, 7.32MB)
테스트 4 〉 통과 (0.29ms, 7.28MB)
테스트 5 〉 통과 (1.87ms, 8.01MB)
테스트 6 〉 통과 (2.46ms, 8.18MB)
테스트 7 〉 통과 (0.16ms, 7.31MB)
테스트 8 〉 통과 (5.62ms, 9.63MB)
테스트 9 〉 통과 (0.50ms, 7.45MB)
테스트 10 〉 통과 (5.42ms, 9.88MB)
테스트 11 〉 통과 (0.15ms, 7.14MB)
테스트 12 〉 통과 (0.11ms, 7.17MB)
테스트 13 〉 통과 (0.13ms, 7.36MB)
테스트 14 〉 통과 (0.13ms, 7.18MB)
테스트 15 〉 통과 (0.05ms, 7.18MB)
테스트 16 〉 통과 (6.27ms, 10.1MB)
테스트 17 〉 통과 (9.43ms, 10.8MB)
테스트 18 〉 통과 (0.18ms, 7.1MB)
테스트 19 〉 통과 (0.06ms, 7.06MB)
테스트 20 〉 통과 (8.96ms, 10.5MB)
테스트 21 〉 통과 (9.14ms, 10.5MB)
테스트 22 〉 통과 (1.29ms, 7.99MB)
테스트 23 〉 통과 (0.03ms, 7.14MB)
테스트 24 〉 통과 (5.55ms, 9.88MB)
테스트 25 〉 통과 (5.71ms, 9.93MB)
테스트 26 〉 통과 (0.02ms, 7.17MB)속도 어쩔... ㅡㅜ.. 파이썬의 편리한 내장 함수와 기본 라이브러리들에 너무 길들여져 있었나 봅니다...
func solution(nums []int) (answer int) {
max := 0
sums := make(map[int]int)
for i := 0; i < len(nums)-2; i++ {
for j := i + 1; j < len(nums)-1; j++ {
for k := j + 1; k < len(nums); k++ {
sum := nums[i] + nums[j] + nums[k]
sums[sum]++
if sum > max {
max = sum
}
}
}
}
primes := make([]bool, max+1, max+1)
primes[0], primes[1], primes[2] = false, false, true
for i := 3; i < max+1; i++ {
primes[i] = true
}
for i := 2; i < max+1; i++ {
if primes[i] {
if v, ok := sums[i]; ok {
answer += v
}
for j := i * 2; j < max+1; j += i {
primes[j] = false
}
}
}
return
}테스트 1 〉 통과 (0.20ms, 7.21MB)
테스트 2 〉 통과 (0.24ms, 7.35MB)
테스트 3 〉 통과 (0.12ms, 7.19MB)
테스트 4 〉 통과 (0.09ms, 7.35MB)
테스트 5 〉 통과 (0.30ms, 6.98MB)
테스트 6 〉 통과 (0.38ms, 7.16MB)
테스트 7 〉 통과 (0.08ms, 7.17MB)
테스트 8 〉 통과 (1.14ms, 7.12MB)
테스트 9 〉 통과 (0.23ms, 7.11MB)
테스트 10 〉 통과 (0.79ms, 7.5MB)
테스트 11 〉 통과 (0.07ms, 7.35MB)
테스트 12 〉 통과 (0.07ms, 7.14MB)
테스트 13 〉 통과 (0.06ms, 7.21MB)
테스트 14 〉 통과 (0.07ms, 7.13MB)
테스트 15 〉 통과 (0.04ms, 7.18MB)
테스트 16 〉 통과 (1.10ms, 7.27MB)
테스트 17 〉 통과 (1.02ms, 7.25MB)
테스트 18 〉 통과 (0.09ms, 7.19MB)
테스트 19 〉 통과 (0.07ms, 7.18MB)
테스트 20 〉 통과 (1.21ms, 7.47MB)
테스트 21 〉 통과 (1.42ms, 7.38MB)
테스트 22 〉 통과 (0.41ms, 7.4MB)
테스트 23 〉 통과 (0.03ms, 7.16MB)
테스트 24 〉 통과 (1.02ms, 7.39MB)
테스트 25 〉 통과 (1.04ms, 7.35MB)
테스트 26 〉 통과 (0.02ms, 7.04MB)3줄 더 줄이기..
(조금 읽기 불편할 수도 있지만 o(1)과 3줄을 얻어봄)
func solution(nums []int) (answer int) {
max := 0
sums := make(map[int]int)
for i := 0; i < len(nums)-2; i++ {
for j := i + 1; j < len(nums)-1; j++ {
for k := j + 1; k < len(nums); k++ {
sum := nums[i] + nums[j] + nums[k]
sums[sum]++
if sum > max {
max = sum
}
}
}
}
noPrimes := make([]bool, max+1, max+1)
noPrimes[0], noPrimes[1] = true, true
for i := 2; i < max+1; i++ {
if !noPrimes[i] {
if v, ok := sums[i]; ok {
answer += v
}
for j := i * 2; j < max+1; j += i {
noPrimes[j] = true
}
}
}
return
}테스트 1 〉 통과 (0.25ms, 7.25MB)
테스트 2 〉 통과 (0.25ms, 7.05MB)
테스트 3 〉 통과 (0.11ms, 7.26MB)
테스트 4 〉 통과 (0.09ms, 7.25MB)
테스트 5 〉 통과 (0.30ms, 7.16MB)
테스트 6 〉 통과 (0.49ms, 7.18MB)
테스트 7 〉 통과 (0.08ms, 7.31MB)
테스트 8 〉 통과 (0.82ms, 7.18MB)
테스트 9 〉 통과 (0.16ms, 7.18MB)
테스트 10 〉 통과 (0.79ms, 7.23MB)
테스트 11 〉 통과 (0.07ms, 7.18MB)
테스트 12 〉 통과 (0.11ms, 7.12MB)
테스트 13 〉 통과 (0.08ms, 7.26MB)
테스트 14 〉 통과 (0.07ms, 7.2MB)
테스트 15 〉 통과 (0.05ms, 7.15MB)
테스트 16 〉 통과 (1.02ms, 7.55MB)
테스트 17 〉 통과 (1.26ms, 7.13MB)
테스트 18 〉 통과 (0.09ms, 7.22MB)
테스트 19 〉 통과 (0.06ms, 7.13MB)
테스트 20 〉 통과 (1.47ms, 7.24MB)
테스트 21 〉 통과 (1.19ms, 7.23MB)
테스트 22 〉 통과 (0.47ms, 7.3MB)
테스트 23 〉 통과 (0.02ms, 7.18MB)
테스트 24 〉 통과 (0.95ms, 7.45MB)
테스트 25 〉 통과 (1.02ms, 7.34MB)
테스트 26 〉 통과 (0.04ms, 7.2MB)
자바
import java.util.HashMap;
class Solution {
public int solution(int[] nums) {
var sums = new HashMap<Integer, Integer>();
int max_sum = 0, answer = 0;
for (var i = 0; i < nums.length - 2; i++)
for (var j = i + 1; j < nums.length - 1; j++)
for (var k = j + 1; k < nums.length; k++) {
var sum = nums[i] + nums[j] + nums[k];
sums.put(sum, sums.getOrDefault(sum, 0) + 1);
if (max_sum < sum) max_sum = sum;
}
var primes = new boolean[max_sum + 1];
primes[0] = false;
primes[1] = false;
for (var i = 2; i <= max_sum; i++) {
primes[i] = true;
}
for (var i = 2; i <= max_sum; i++) {
if (primes[i]) {
if (sums.containsKey(i)) answer += sums.get(i);
for (var j = i * 2; j <= max_sum; j += i)
primes[j] = false;
}
}
return answer;
}
}반응형