코딩 테스트/Level 2
18. 소수 찾기
컴닥
2020. 8. 1. 23:59
반응형
https://programmers.co.kr/learn/courses/30/lessons/42839
코딩테스트 연습 - 소수 찾기
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 �
programmers.co.kr
파이썬
from itertools import permutations
def solution(numbers):
numbers_set = {int("".join(i)) for r in range(1, len(numbers)+1) for i in permutations(numbers, r)}
max_num = max(numbers_set)
a = [False, False] + [True] * (max_num - 1)
primes = set()
for i in range(2, max_num + 1):
if a[i]:
primes.add(i)
for j in range(2 * i, max_num + 1, i):
a[j] = False
return len(primes & numbers_set)테스트 1 〉 통과 (0.61ms, 10.9MB)
테스트 2 〉 통과 (112.58ms, 20.8MB)
테스트 3 〉 통과 (0.07ms, 10.9MB)
테스트 4 〉 통과 (53.99ms, 16.6MB)
테스트 5 〉 통과 (837.15ms, 61.6MB)
테스트 6 〉 통과 (0.07ms, 10.8MB)
테스트 7 〉 통과 (0.61ms, 11MB)
테스트 8 〉 통과 (1416.37ms, 95.3MB)
테스트 9 〉 통과 (0.11ms, 10.9MB)
테스트 10 〉 통과 (169.07ms, 25.7MB)
테스트 11 〉 통과 (16.21ms, 12.5MB)
테스트 12 〉 통과 (9.39ms, 12MB)리스트 컴프리헨션 내의 2중 for 문은 실전에선 애매합니다.
다시 보면 좀 혼란스럽습니다...
리턴 문에서 교집합 연산을 제거하고,
한 줄을 더 늘려 속도가 올렸습니다.
from itertools import permutations
def solution(numbers):
answer = 0
numbers_set = {int("".join(i)) for r in range(1, len(numbers)+1) for i in permutations(numbers, r)}
max_num = max(numbers_set)
a = [False, False] + [True] * (max_num - 1)
for i in range(2, max_num + 1):
if a[i]:
if i in numbers_set:
answer += 1
for j in range(2 * i, max_num + 1, i):
a[j] = False
return answer테스트 1 〉 통과 (0.55ms, 10.9MB)
테스트 2 〉 통과 (113.78ms, 20.8MB)
테스트 3 〉 통과 (0.07ms, 10.9MB)
테스트 4 〉 통과 (50.82ms, 15.4MB)
테스트 5 〉 통과 (721.26ms, 61.5MB)
테스트 6 〉 통과 (0.06ms, 10.9MB)
테스트 7 〉 통과 (0.59ms, 10.9MB)
테스트 8 〉 통과 (1079.97ms, 95.5MB)
테스트 9 〉 통과 (0.12ms, 10.9MB)
테스트 10 〉 통과 (177.72ms, 25.7MB)
테스트 11 〉 통과 (15.29ms, 12.2MB)
테스트 12 〉 통과 (8.19ms, 11.4MB)집합 자료형과 에라스토테네스의 채로 나름 최적화했지만..
다른 분의 코드를 보니... (와우~! 이 건 뭐지?)
코드량은 절반, 속도는 최대 2배가량 빠름~! ㄷㄷㄷㄷ
집합에서 요소를 바로 제거해주었네요.. 왜 이 생각을 못했을까..
from itertools import permutations
def solution(numbers):
numbers_set = {int("".join(i)) for r in range(1, len(numbers)+1) for i in permutations(numbers, r)}
numbers_set -= {0, 1}
for i in range(2, int(max(numbers_set) **0.5) + 1):
numbers_set -= set(range(2 * i, max(numbers_set) + 1, i))
return len(numbers_set)테스트 1 〉 통과 (0.53ms, 11.1MB)
테스트 2 〉 통과 (73.84ms, 44.8MB)
테스트 3 〉 통과 (0.09ms, 11MB)
테스트 4 〉 통과 (49.31ms, 20.5MB)
테스트 5 〉 통과 (191.92ms, 146MB)
테스트 6 〉 통과 (0.07ms, 10.9MB)
테스트 7 〉 통과 (0.64ms, 11MB)
테스트 8 〉 통과 (528.21ms, 281MB)
테스트 9 〉 통과 (0.10ms, 10.9MB)
테스트 10 〉 통과 (338.50ms, 51.8MB)
테스트 11 〉 통과 (26.02ms, 14.5MB)
테스트 12 〉 통과 (4.88ms, 13.9MB)GO
import (
"sort"
"strconv"
"strings"
)
func count(nums string) map[rune]int {
numCount := make(map[rune]int)
for _, v := range nums {
numCount[v]++
}
return numCount
}
func solution(numbers string) (rtn int) {
// numbers에서 사용된 숫자의 개수 카운트
numCount := count(numbers)
// 종이에서 나올 수 있는 최대값을 구함.
numStr := strings.Split(numbers, "")
sort.Sort(sort.Reverse(sort.StringSlice(numStr)))
max, _ := strconv.Atoi(strings.Join(numStr, ""))
// 에라토스테네스의 체
// true로 초기화하기 번거로우니, 반대로 소수아님 == true 으로함)
notPrimes := make([]bool, max+1)
notPrimes[0], notPrimes[1] = true, true
for i := 2; i <= max; i++ {
if notPrimes[i] { // 소수가 아닌 경우
continue
}
for j := i * 2; j <= max; j += i {
notPrimes[j] = true
}
success := true // 성공 여부를 확인할 체커
// 소수에서 사용된 숫자의 개수 카운트
primeCount := count(strconv.Itoa(i))
// 소수와 numbers의 사용 숫자 개수 비교
for k, primeV := range primeCount {
if numV, ok := numCount[k]; !ok || primeV > numV {
success = false
break
}
}
if success == true {
rtn++
}
}
return
}테스트 1 〉 통과 (0.30ms, 7.23MB)
테스트 2 〉 통과 (29.96ms, 11.2MB)
테스트 3 〉 통과 (0.04ms, 7.16MB)
테스트 4 〉 통과 (15.79ms, 10.9MB)
테스트 5 〉 통과 (134.97ms, 15.6MB)
테스트 6 〉 통과 (0.05ms, 7.25MB)
테스트 7 〉 통과 (0.31ms, 7.32MB)
테스트 8 〉 통과 (213.74ms, 19.9MB)
테스트 9 〉 통과 (0.09ms, 7.15MB)
테스트 10 〉 통과 (41.91ms, 11.1MB)
테스트 11 〉 통과 (5.71ms, 9.4MB)
테스트 12 〉 통과 (3.63ms, 8.54MB)느린 느낌이라.. 조금이나마 속도를 올리기 위해 몇 줄 추가해 보았습니다.
import (
"sort"
"strconv"
"strings"
)
func solution(numbers string) (rtn int) {
numCount := make(map[rune]int)
for _, v := range numbers {
numCount[v]++
}
numStr := strings.Split(numbers, "")
sort.Sort(sort.Reverse(sort.StringSlice(numStr)))
max, _ := strconv.Atoi(strings.Join(numStr, ""))
notPrimes := make([]bool, max+1)
notPrimes[0], notPrimes[1] = true, true
for i := 2; i <= max; i++ {
if !notPrimes[i] {
for j := i * 2; j <= max; j += i {
notPrimes[j] = true
}
}
}
for i, v := range notPrimes {
if v { // 소수가 아닌 경우
continue
}
success := true
primeCount := make(map[rune]int)
for _, primeNum := range strconv.Itoa(i) {
if _, ok := numCount[primeNum]; !ok {
success = false
break
}
primeCount[primeNum]++
}
if success == false {
continue
}
for primeNum, v := range primeCount {
if v > numCount[primeNum] {
success = false
break
}
}
if success == true {
rtn++
}
}
return
}테스트 1 〉 통과 (0.11ms, 11MB)
테스트 2 〉 통과 (11.53ms, 10.4MB)
테스트 3 〉 통과 (0.03ms, 9.11MB)
테스트 4 〉 통과 (4.19ms, 9.59MB)
테스트 5 〉 통과 (44.55ms, 16.3MB)
테스트 6 〉 통과 (0.04ms, 9.33MB)
테스트 7 〉 통과 (0.12ms, 9.04MB)
테스트 8 〉 통과 (69.71ms, 19.5MB)
테스트 9 〉 통과 (0.07ms, 11.1MB)
테스트 10 〉 통과 (15.26ms, 11.1MB)
테스트 11 〉 통과 (1.59ms, 9.32MB)
테스트 12 〉 통과 (1.03ms, 9.14MB)코드가 장황해졌지만 속도는 약 3배 정도 빨라졌습니다.
좀 더 깔끔하게 코드를 쓰고 싶지만 제 실력의 한계군요.
순열 없이 문제를 풀어보고 싶어서...
고 언어의 맵을 이용하면 될 것 같아 시도해 보았습니다만...
결과는... 그냥 그렇습니다.
C#
위 GO 코드를 C#에서 재작성해보았는데요..
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public int solution(string numbers)
{
int answer = 0;
int max = int.Parse(string.Join("", numbers.OrderByDescending(c => c).ToArray()));
bool[] notPrimes = new bool[max + 1];
for (int i = 2; i <= max; i++)
{
if (notPrimes[i] == true)
continue;
for (int j = i * 2; j <= max; j += i)
notPrimes[j] = true;
}
Dictionary<char, int> numCount = new Dictionary<char, int>();
foreach (char c in numbers)
{
if (!numCount.ContainsKey(c))
numCount.Add(c, 1);
else
numCount[c]++;
}
for (int i = 2; i < notPrimes.Length; i++)
{
if (notPrimes[i] == true)
continue;
Dictionary<char, int> temp = new Dictionary<char, int>();
bool success = true;
foreach (char c in i.ToString())
{
if (!numCount.ContainsKey(c))
{
success = false;
break;
}
if (!temp.ContainsKey(c))
temp.Add(c, 1);
else
temp[c]++;
}
if (success == false)
continue;
foreach (char c in temp.Keys)
if (temp[c] > numCount[c])
{
success = false;
break;
}
if (success == true)
answer++;
}
return answer;
}
}테스트 1 〉 통과 (20.80ms, 54.8MB)
테스트 2 〉 통과 (54.43ms, 57.5MB)
테스트 3 〉 통과 (20.30ms, 55MB)
테스트 4 〉 통과 (34.80ms, 57.2MB)
테스트 5 〉 통과 (113.10ms, 60.2MB)
테스트 6 〉 통과 (21.48ms, 54.8MB)
테스트 7 〉 통과 (20.24ms, 59.1MB)
테스트 8 〉 통과 (176.82ms, 62.2MB)
테스트 9 〉 통과 (20.66ms, 55MB)
테스트 10 〉 통과 (59.44ms, 59MB)
테스트 11 〉 통과 (24.23ms, 56.9MB)
테스트 12 〉 통과 (22.86ms, 54.9MB)순열을 이용하니 코드량은 많이 주네요...
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
static List<int> numberList = new List<int>();
public int solution(string numbers)
{
List<int> primeList = new List<int>();
for (int i = 1; i <= numbers.Length; i++)
Perm(numbers.ToCharArray(), 0, numbers.Length, i);
numberList = numberList.Distinct().ToList();
int max = numberList.Max();
bool[] notPrimes = new bool[max + 1];
for (int i = 2; i <= max; i++)
{
if (notPrimes[i] == false)
primeList.Add(i);
for (int j = i * 2; j <= max; j += i)
notPrimes[j] = true;
}
return Enumerable.Intersect(numberList, primeList).Count();
}
public static void Perm(char[] arr, int depth, int n, int k)
{
if (depth == k)
{
numberList.Add(int.Parse(string.Join("", arr.Take(k))));
return;
}
for (int i = depth; i < n; i++)
{
char temp = arr[i];
arr[i] = arr[depth];
arr[depth] = temp; Perm(arr, depth + 1, n, k);
temp = arr[i];
arr[i] = arr[depth];
arr[depth] = temp;
}
}
}테스트 1 〉 통과 (19.33ms, 56.7MB)
테스트 2 〉 통과 (40.16ms, 56MB)
테스트 3 〉 통과 (18.02ms, 57MB)
테스트 4 〉 통과 (29.80ms, 52.6MB)
테스트 5 〉 통과 (155.72ms, 67.7MB)
테스트 6 〉 통과 (19.15ms, 58.5MB)
테스트 7 〉 통과 (19.73ms, 54.7MB)
테스트 8 〉 통과 (275.99ms, 78.7MB)
테스트 9 〉 통과 (19.53ms, 54.9MB)
테스트 10 〉 통과 (45.78ms, 58.4MB)
테스트 11 〉 통과 (22.18ms, 57.1MB)
테스트 12 〉 통과 (19.97ms, 56.9MB)하지만 속도 어쩔....
처음 어느 분의 파이썬 코드처럼 효율적으로 정리하는 방법을 찾아야 할 것 같은데....
그건.. 다른 분들의 풀이를 참고하시길 바라며..
반응형