[프로그래머스] 소수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/42839

순열로 푸는건 알았는데
순열로 푸는 것만 알아서 챗지피티한테 물어보고 풀었다

물론 파이썬의 permutations 모듈을 쓰기는 했지만,
순열을 직접 구현하는 방법도 알아야 할 것 같아서 C로 구현해보았다
이제 이해가 좀 되는 것 같음

#include <stdio.h>

void swap(int* a, int* b) 
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void permute(int* arr, int n, int depth)
{
    if (n == depth) {
        for (int i = 0; i < n; i++) {
            printf("%d ", arr[i]);
        }
        printf("\n");
    } else {
        for (int i = depth; i < n; i++) {  
            swap(&arr[depth], &arr[i]);
            permute(arr, n, depth + 1);
            swap(&arr[depth], &arr[i]);
        }
    }
}

int main() {
    int arr[] = {1, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    permute(arr, n, 0);
    return 0;
}

이건 답인데
set 자료구조를 알고만 있지 활용할줄은 모르는 것 같아서 다시 찾아봤다.

import math
from itertools import permutations

def solution(numbers):
    answer = 0
    
    def isPrime(n):
        if n < 2:
            return False
        for i in range(2, int(math.sqrt(n)) + 1):
            if n % i == 0:
                return False
        return True
    
    unique_numbers = set()
    
    for i in range(1, len(numbers) + 1):
        perms = permutations(numbers, i)
        for perm in perms:
            num = int(''.join(perm))
            unique_numbers.add(num)
    
    answer = sum(1 for num in unique_numbers if isPrime(num))
        
    return answer

참고
ChatGPT
https://programming4myself.tistory.com/94