18. 소수 찾기

코딩 테스트/Level 2 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)

하지만 속도 어쩔....
처음 어느 분의 파이썬 코드처럼 효율적으로 정리하는 방법을 찾아야 할 것 같은데....
그건.. 다른 분들의 풀이를 참고하시길 바라며..

ABOUT ME

ComDoc ComDoc

파이썬

GO

C#

티스토리툴바

ABOUT ME

파이썬

GO

C#

관련글 관련글 더보기

티스토리툴바