ABOUT ME

    -

    Today
    -
    Yesterday
    -
    Total
    -
    • 41. 소수 만들기
      코딩 테스트/Level 2 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;
    }
}
      반응형

      관련글 관련글 더보기

    Designed by Tistory.

    티스토리툴바