꾸준히 개발하기

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

잘못된 접근

DP로 접근했는데 애초에 재귀를 보면서 분명 같은 경우를 살펴볼 일이 없어야 하는데... 같은 경우를 체크한다...ㅠㅠㅠ 

실패한 소스코드

import copy

frodo = [0 for _ in range(11)]
answer = []
max_gap = 0

def cmpScore(frodo, apeach):
    score_f = 0
    score_ap = 0
    for i in range(11):
        if frodo[i] > apeach[i]:
            score_f += 10-i
        elif frodo[i] <= apeach[i] and apeach[i] != 0:
            score_ap += 10-i
        else:
            continue
    return score_f - score_ap

def isFrodoWinner(frodo, apeach):
    score_f = 0
    score_ap = 0
    for i in range(11):
        if frodo[i] > apeach[i]:
            score_f += 10-i
        elif frodo[i] <= apeach[i] and apeach[i] != 0:
            score_ap += 10-i
        # k점에 아무도 못 맞힌 경우
        else:
            continue
    if score_f > score_ap:
        return True
    else:
        return False
    
def shoot(score, n, info):
    global max_gap
    # 해당 점수 맞히는 경우
    frodo[10-score] = info[10-score] + 1
    if sum(frodo) == n:
        # print(frodo, isFrodoWinner(frodo, info))
        if isFrodoWinner(frodo, info):
            if len(answer) == 0:
                answer.append(copy.deepcopy(frodo))
                max_gap = cmpScore(frodo, info)
            else:
                if max_gap < cmpScore(frodo, info):
                    answer.clear()
                    answer.append(copy.deepcopy(frodo))
                    max_gap = cmpScore(frodo, info)
                elif max_gap == cmpScore(frodo, info):
                    answer.append(copy.deepcopy(frodo))
            return
    
    elif sum(frodo) > n:
        frodo[10-score] = 0
        if score - 1 < 0:
            return
        else:
            shoot(score-1, n, info)
    else:
        if score - 1 < 0:
            return
        else:
            shoot(score-1, n, info)
    
    # 해당 점수 안맞히고 넘어가는 경우
    frodo[10-score] = 0
    if score - 1 < 0:
        return
    else:
        shoot(score-1, n, info)

def solution(n, info):
    shoot(10, n, info)
    
    if len(answer) == 0:
        answer.append([-1])
    else:
        answer.sort(key=lambda x:(-x[10], -x[9], -x[8], -x[7], -x[6], -x[5], -x[4], -x[3], -x[2], -x[1], -x[0]))            
    print(answer)
    return answer[0]

올바른 접근

완전 탐색으로 접근

0점부터 10점까지 모든 점수를 획득할지 말지만 결정하면 되므로 모든 경우의 수는 2^11 로 충분히 살펴볼 수 있다. 2시간 넘게 DP로 끙끙 앓았더니 슬프다. 운동하고 와서 다른 사람 코드 좀 보고... 카카오 코테 보기 전날 한번 더 완탐 문제들 풀어볼 때 다시 봐야겠다. 아직 문제 유형을 파악하는데 서툴구만 흑

BFS 접근

1. 10점부터 0점까지 화살 쏨

현재 몇점인지 : score ( 0 -> 10점과녁)

현재 라이언 과녁 상황 : lion [0 for _ in range(11)]

2. 어피치를 이기려면

 1) 어피치보다 +1발

 2) 해당 점수 포기

* 주의할 점은 그냥 '=' 연산자 써서는 X. copy() 메소드로 깊은 복사 해주자.

( 2차원 이상의 배열을 깊은 복사 해주려면 copy 라이브러리의 deepcopy() 메소드 써야한다. 리스트의 copy() 메소드는 1차원까지만 깊은 복사 지원 )

3. 조건 체크

 1) 화살을 n발보다 더 쏜 경우 ( sum(lion) > n ) : 패스

 2) 0점까지 갔는데 다 못 쏜 경우 ( score == 10 ): 마지막 과녁에 다 쏘기

 3) 다 쏜 경우 ( sum(lion) == n ) : 점수 계산. 최대 점수차 갱신해가면서 최대 점수차를 내는 경우만 따로 배열로 저장하기

4. shoot() 함수를 실행한뒤 최종 조건 체크

 1) 리턴값이 빈 배열인 경우 : [-1] 리턴

 2) 리턴값 배열의 길이가 1인 경우 : 해당 배열 리턴

 3) 그 외의 경우 : 가장 낮은 점수를 많이 맞힌 경우 리턴.

  * score을 통해 가장 높은 점수부터 쏘기 시작했으므로 배열의 가장 마지막 요소가 해당됨.

python 코드

from collections import deque


def shoot(n, info):
    q = deque([(0, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])])
    result = []  # 가능한 시나리오 모두 저장
    max_gap = 0  # 최대 점수차

    while q:
        score, lion = q.popleft()

        # 화살 다 쐈으니 점수 계산
        if sum(lion) == n:
            score_ap, score_l = 0, 0
            for i in range(11):
                if not (info[i] == 0 and lion[i] == 0):
                    if info[i] >= lion[i]:
                        score_ap += 10 - i
                    else:
                        score_l += 10 - i

            if score_ap < score_l:
                gap = score_l - score_ap
                if max_gap > gap:
                    continue
                if max_gap < gap:
                    max_gap = gap
                    result.clear()
                result.append(lion)
        # 화살을 n발보다 더 쏜 경우
        elif sum(lion) > n:
            continue

        # 마지막 과녁까지 간 경우, 화살 마지막 과녁에 다 쏘기
        elif score == 10:
            tmp = lion.copy()
            tmp[score] = n - sum(tmp)
            q.append((-1, tmp))

        # 슛슛슛
        else:
            # 어피치보다 1발 더
            shoot_lion = lion.copy()
            shoot_lion[score] = info[score] + 1
            q.append((score + 1, shoot_lion))
            # 해당 점수 포기, 패스
            giveup_lion = lion.copy()
            giveup_lion[score] = 0
            q.append((score + 1, giveup_lion))

    return result


def solution(n, info):
    answer = []

    all_cases = shoot(n, info)

    if len(all_cases) == 0:
        answer.append(-1)
    elif len(all_cases) == 1:
        answer = all_cases[0]
    else:
        answer = all_cases[-1]
    return answer

언제쯤 익숙해지냐 완전탐색.. BFS... DFS...  끙

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

풀이

조건에 맞춰서 차근차근 구현만 하면 되는 문제였다.

파이썬 내 올림 기능을 지원하는 메소드가 math.ceil 인데 실수로 반올림하는 round() 메서드를 썼다... 주의하자!

먼저 수도코드로 쭉 작성한 뒤 구현했고, 바로 통과됬다.

1. records 내 값을 공백 기준으로 split해서 time, car_num, inout에 넣기

2. 딕셔너리에 car_num을 키로 time 넣어주기. 각 딕셔너리 value값은 배열. (in, out 순서로 들어간다)

 * 만약 배열 길이가 홀수면 출차 내역이 입력되지 않은 요소이므로 23:59를 직접 넣어준다

3. records 배열 순회가 끝나면 딕셔너리를 살펴보면서 시간을 계산한다.

 - [짝수] : IN / [홀수] : OUT 이므로 홀수 - 짝수 해주면 된다.

   인자를 받아올 때 ":"를 기준으로 hour, min을 쪼개주었다.

   시간은 상관없는데 분은 음수값이 나왔을 때 예외처리를 해주자. (hour -= 1, min += 60)

4. 총 누적시간이 기본 시간을 넘는다면 문제 조건대로 계산하고, 넘지 않는다면 기본 요금을 저장한다.

 * 여기에서 문제 조건 상 차량번호가 작은 요소부터 출력해달라고 했으므로 [차량번호, 요금] 을 저장하는 배열을 만들어준 뒤 차량번호를 기준으로 정렬한 뒤 요금값을 차례대로 answer에 넣어주자.

python 코드

import math
def solution(fees, records):
    carnum_fee = [] # (차량번호, 요금) 순 저장
    car_dict = {}
    
    for r in records:
        time, car_num, inout = r.split(" ")
        if car_num in car_dict:
            car_dict[car_num].append(time)
        else:
            car_dict[car_num] = [time]
    
    
    for k in car_dict.keys():
        # 출차 기록이 없는 경우
        if len(car_dict[k]) % 2 != 0:
            car_dict[k].append("23:59")
        
        # 시간 계산
        total_time = 0
        for i in range(0, len(car_dict[k]), 2):
            # OUT : i+1, IN : i
            out_h, out_m = map(int,car_dict[k][i+1].split(":"))
            in_h, in_m = map(int, car_dict[k][i].split(":"))
            
            hour = out_h - in_h
            minute = out_m - in_m
            
            if minute < 0:
                hour -= 1
                minute += 60
            
            total_time += hour * 60 + minute

        # 요금 계산
        if total_time > fees[0]:
            carnum_fee.append([k, fees[1] + math.ceil((total_time-fees[0]) / fees[2]) * fees[3]])
        else:
            carnum_fee.append([k, fees[1]])
    
    carnum_fee.sort(key = lambda x : x[0])
    
    answer = [v[1] for v in carnum_fee]
    return answer

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

풀이

진법변환, 소수판별은 자주 등장하는 부분이라 비교적 쉽게 구현했다. 소수의 판별 조건이 약간 까다로웠는데 가능한 시나리오들을 차근차근 생각해봤다.

1. 진법변환

2. 앞에서부터 살펴보는데

 1) 맨 앞인 경우 -> P0, P 케이스가 등장할 수 있다.

    - P0 : 뒷 숫자에서 0이 등장하는 경우, 그 앞까지의 숫자가 소수인지 체크

    - P : 숫자 끝까지 0이 등장하지 않는 경우, 해당 숫자 자체가 소수인지 체크

 2) 0이 한번이라도 등장한 경우 -> 0P0, 0P 케이스가 등장할 수 있다.

   - 0P0 : 0이 한번 더 등장한 경우, 0과 0 사이의 숫자가 소수인지 체크

   - 0P : 숫자 끝까지 0이 한번 더 등장하지 않은 경우, 0 뒤의 숫자가 소수인지 체크

따라서 가능한 경우를 flag로 만들어서 체크해줘야 할 때마다 체크해줬다. 요즘 디버깅 안하고 프로그래머스 내에서 최대한 풀어보려고 하다 보니 print 문을 섞어서 실행했다. 두가지 버전 모두 기록해두려고 한다!

주의할 점은 소수인지 체크할 숫자를 담는 문자열이 빈 문자열인 경우 소수 체크를 하지 않고 넘어가줘야 한다. (코드 내 check_num != '' 조건)

ex. P0 경우가 등장하여 check_num이 빈 문자열로 초기화되었는데 그 뒤에 다시 0이 등장하면 빈 문자열이 isPrime 함수로 넘어가 형변환 에러가 발생한다. 

python 코드 (print 출력문 O)

# 진법 변환
def convert(n, k):
    result = ''
    q, r = divmod(n, k)
    result += str(r)
    
    while q != 0:
        q, r = divmod(q, k)
        result += str(r)
    
    return result[::-1]

# 소수 판별 (제곱근까지만 판단)
def isPrime(num):
    if num == 0 or num == 1:
        return False
    for i in range(2, int(num**0.5)+1):
        if num % i == 0:
            # 소수 아님
            return False    
    return True

def solution(n, k):
    answer = 0
    
    converted_n = convert(n, k)
    
    check_num = ''
    
    flag_0P0 = False
    flag_P0 = False
    flag_0P = False
    flag_P = False
    
    for i in range(len(converted_n)):
        print("------")
        print(flag_0P0,flag_P0,flag_0P,flag_P)
        print(check_num)
        print("------")
        
        # 맨 앞인 경우
        if i == 0:
            # P0, P 가능
            check_num += converted_n[i]
            flag_P, flag_P0 = True, True
            continue
        
        if converted_n[i] == '0':
            flag_P = False
            flag_0P = True
            # 만약 맨앞에서부터 보던 중이었다면
            if flag_P0:
                print("PO case", check_num)
                if isPrime(int(check_num)):
                    print("PO Hit", check_num)
                    answer += 1
                check_num = ''
                flag_0P0, flag_P0 = True, False
                continue
            
            # 한번이라도 0이 등장한 적이 있다면
            elif flag_0P0 and check_num != '':
                print("0PO case", check_num)
                if isPrime(int(check_num)):
                    print("0PO Hit", check_num)
                    answer += 1
                check_num = ''
        else:
            check_num += converted_n[i]
        
    
    # 맨 뒤까지 다 봤는데 0이 안나온 경우였다면, P 경우 체크
    if flag_P and check_num != '' and isPrime(int(check_num)) :
        answer += 1
        print("P Hit", check_num)
    # 맨 뒤까지 다 봤고 0P가 가능한 경우
    if flag_0P and check_num != '' and isPrime(int(check_num)) :
        answer += 1
        print("0P Hit", check_num)
        
    return answer

python 코드 (깔끔 ver)

# 2022-09-20
# 2022 카카오 테크 인턴십 기출 - k진수에서 소수 개수 구하기 (프로그래머스 lv2)
# https://school.programmers.co.kr/learn/courses/30/lessons/92335
# 소요 시간 : 15:17 ~ 16:06, 16:21~16:31 (60m)

# 진법 변환
def convert(n, k):
    result = ""
    q, r = divmod(n, k)
    result += str(r)

    while q != 0:
        q, r = divmod(q, k)
        result += str(r)

    return result[::-1]


# 소수 판별 (제곱근까지만 판단)
def isPrime(num):
    if num == 0 or num == 1:
        return False
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            # 소수 아님
            return False
    return True


def solution(n, k):
    answer = 0

    converted_n = convert(n, k)

    check_num = ""

    flag_0P0 = False
    flag_P0 = False
    flag_0P = False
    flag_P = False

    for i in range(len(converted_n)):
        # 맨 앞인 경우
        if i == 0:
            # P0, P 가능
            check_num += converted_n[i]
            flag_P, flag_P0 = True, True
            continue

        if converted_n[i] == "0":
            flag_P = False
            flag_0P = True
            # 만약 맨앞에서부터 보던 중이었다면
            if flag_P0:
                if isPrime(int(check_num)):
                    answer += 1
                check_num = ""
                flag_0P0, flag_P0 = True, False
                continue

            # 한번이라도 0이 등장한 적이 있다면
            elif flag_0P0 and check_num != "":
                if isPrime(int(check_num)):
                    answer += 1
                check_num = ""
        else:
            check_num += converted_n[i]

    # 맨 뒤까지 다 봤는데 0이 안나온 경우였다면, P 경우 체크
    if flag_P and check_num != "" and isPrime(int(check_num)):
        answer += 1
    # 맨 뒤까지 다 봤고 0P가 가능한 경우
    if flag_0P and check_num != "" and isPrime(int(check_num)):
        answer += 1

    return answer

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

풀이

두 큐의 합을 같게 만들어주려면, 합이 더 큰 큐에서 pop해가면서 중간값을 맞춰봐야 최소횟수.

이 과정에서 완전히 빈 큐가 생겨버리면 두 큐의 합을 같게 만들 수 없는 것이므로 -1을 리턴해주면 된다.

로직 자체는 맞게 접근한 것 같은데 테스트케이스 몇개가 계속 시간초과가 나서 파이썬 메서드의 시간복잡도를 봤더니 답이 나왔다.

배열의 가장 앞의 요소를 pop해주기 위해 배열 자료형의 pop(0) 메서드를 사용했는데, pop() 연산 자체는 복잡도가 O(1)인데 pop(0)은 O(n)이다. 그 이유는 맨 앞에 있는 값을 출력해주기 위해 전체 복사를 하기 때문이다..! 따라서 리스트 말고 deque를 사용하여 pop(0) 대신 popleft()를 사용하는 것이 시간복잡도 상 매우 유리하다.

자료형을 list -> deque로 바꾸고 테스트케이스 22~24번이 해결됬으며,

최대 가능한 횟수를 모든 요소끼리 서로 다 바꿔도 안될 때 (리스트의 최대길이만큼 교환했을 때) 300,000번으로 제한해두니 테스트케이스 11, 28번이 해결되었다.

sum() 메서드와 len() 메서드 역시 매번 연산해줄 필요는 없어서 산술연산만 할 수 있게 코드를 약간 길게 적었다.

python 코드

from collections import deque
def solution(queue1, queue2):
    answer = 0
    
    deque1 = deque(queue1)
    deque2 = deque(queue2)
    
    sum1 = sum(queue1)
    sum2 = sum(queue2)
    
    len1 = len(queue1)
    len2 = len(queue2)
    
    goal = (sum1 + sum2) / 2
    
    while len1 != 0 and len2 != 0:
        if sum1 == goal and sum2 == goal:
            return answer
        
        if answer > 300000:
            break
            
        if sum1 > sum2:
            value = deque1.popleft()
            deque2.append(value)
            sum1 -= value
            sum2 += value
            len1 -= 1
            len2 += 1
        elif sum1 < sum2:
            value = deque2.popleft()
            deque1.append(value)
            sum1 += value
            sum2 -= value
            len1 += 1
            len2 -= 1
        else:
            if sum1 == goal and sum2 == goal:
                return answer
            
        answer += 1
    
    answer = -1
            
    return answer

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

풀이

문제에서 시키는 대로 차근차근 구현하면 되는 문제다.

input 이해

survey[i][0] : i+1번 질문 비동의 선택 시 성격유형

survey[i][1] : i+1번 질문 동의 선택 시 성격유형

choices[i] : 4로 나눈 몫이 1 이상 : 동의 -> survey[i]의 [1] 유형에 4로 나눈 나머지 점수 부여 ('모르겠음' 선택지는 0점인데 나머지도 0점이라 케이스를 쪼개지 않아도 괜찮음)

choices[i] : 4로 나눈 몫이 1 미만 : 비동의 -> survey[i]의 [0] 유형에 (4 - choices[i]) 점수 부여 

지표 체크

각각의 성격유형을 key-value 형태로 저장하는 것이 검색에 수월하여 dictionary 형태를 사용하였다. 다른 사람의 풀이를 보니 많이들 비슷하게 접근했더라.

python 코드

def solution(survey, choices):
    answer = ''
    
    score = {'R': 0, 'T': 0, 'C' : 0, 'F': 0, 'J': 0, 'M': 0, 'A': 0, 'N': 0}
    
    # 점수 부여
    for i in range(len(choices)):
        # 동의
        if choices[i] // 4 >= 1:
            score[survey[i][1]] += choices[i] % 4
        # 비동의
        else:
            score[survey[i][0]] += (4 - choices[i])
    
    # 지표별 유형 판단
    if score['R'] >= score['T']:
        answer += 'R'
    else:
        answer += 'T'
    
    if score['C'] >= score['F']:
        answer += 'C'
    else:
        answer += 'F'
        
    if score['J'] >= score['M']:
        answer += 'J'
    else:
        answer += 'M'
        
    if score['A'] >= score['N']:
        answer += 'A'
    else:
        answer += 'N'
        
    
    return answer

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

접근

유일성을 만족하기 위해 set 자료형을 사용했다. 키의 최대 길이가 8개로, 가능한 키 조합을 모두 구해 각 경우별로 set 자료형으로 변환해도 길이가 변하지 않는 것을 체크했다.

2차원 배열은 set연산을 적용하기가 골치 아파 중간에 한번 tuple 자료형으로 변환해주었다. 

유일성을 만족하는 모든 경우의 수를 ck_list 배열에 저장한 뒤, ck_list 배열을 돌면서 최소성을 만족하는지 체크했다.

최소성을 만족하는지 체크하기 위해 실제로 최소성을 만족하는 후보키 배열 ck를 만들었다. 모든 후보키에 대해 합집합을 수행해 키가 최소성을 만족하는 경우를 체크했다. (단순히 합집합 한번만 했더니 [(0), (1,2)]과 [1,2,3] 경우를 계산하는 과정에서 0, (1,2,3) 이 조건을 만족하는 것으로 되서 cnt 변수를 통해 모든 후보키에 대해서 고려하도록 수정했다.)

한시간정도 걸린 문제였다. 은근 어려워..! 

코드

from itertools import combinations

def solution(relation):
    answer = 0
    
    column_list = [i for i in range(len(relation[0]))]

    # 모든 후보키가 될 수 있는 경우의 수(컬럼 인덱스 배열)
    cases = []
    for i in range(1, len(column_list)+1):
        cases.append(list(combinations(column_list, i)))
        
    ck_list = [] 
    for case_list in cases:
        for case in case_list:
            all_senario = []
            for row in range(len(relation)):
                arr = [relation[row][c] for c in case]
                all_senario.append(tuple(arr))
            # print(all_senario)
            
            if len(all_senario) == len(list(set(all_senario))):
                ck_list.append(case)
        
    # print(ck_list)
    
    ck = []
    for key in ck_list:
        if len(ck) == 0:
            ck.append(key)
            continue
        cnt = 0
        for k in ck:
            if set(key) != set(k) | set(key):
                cnt += 1
        
        if cnt == len(ck):
            ck.append(key)
            
    answer = len(ck)        
    return answer

효율성은 없네 경우의 수를 모두 고려해야되서 그런가?

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

풀이

자기 뒤에서 자기보다 작은 가격이 등장한 최초의 순간만 찾으면 되는 간단한 문제라고 생각했는데......... .... 계속 시간초과가 나서 2시간정도 삽질하다가 해설을 봤다. deque 자료구조를 쓰거나 stack을 사용하면 되는 문제라고 한다. 

아래는 효율성 0점의 눈물나는 코드다.

# 단순 리스트 순회
def solution(prices):
    answer = []
    for i in range(len(prices)):
        cnt = 0
        for j in prices[i + 1 :]:
            if j < prices[i]:
                cnt += 1
                break
            else:
                cnt += 1
        answer.append(cnt)
    return answer

와 충격적... 알고리즘 오카방에 물어봤더니 알려줬다

for j in prices[i + 1 :]:

위 부분에서 매번 리스트를 새롭게 만들어주는 과정에서 시간초과가 난 것이다... 와 ... 그러고 보니 리스트 슬라이싱은 추출하여 새로운 리스트를 만들어주는 것이었다.... 그래서 이 부분 수정하면 효율성을 통과하기는 한다 대박사건

def solution(prices):
    answer = []
    for i in range(len(prices)):
        cnt = 0
        for j in range(i + 1, len(prices)):
            cnt += 1
            if prices[j] < prices[i]:
                break
        answer.append(cnt)
    return answer

deque 사용

list로 순회하는 방법에서 deque를 쓰는 방식으로 바꿨더니 바로 통과가 됬다. 분명 알고리즘은 똑같은데 이게 자료구조...?

# deque 사용
from collections import deque
def solution_deque(prices):
    queue = deque(prices)
    answer = []
    while queue:
        price = queue.popleft()
        cnt = 0
        for j in queue:
            cnt += 1
            if j < price:
                break
        answer.append(cnt)
    return answer

코드 실행 시간이 절반으로 줄었다... 더 효율적인 코드가 무엇일지 계속 고민하는 개발자가 되자

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

풀이

모든 경우의 수를 permutations를 사용하여 순열로 뽑아내었다. list로 나온 요소를 모두 join 메서드를 사용하여 이어붙인 뒤 숫자로 변환하였다. 문제에서 011과 11은 같은 숫자라고 명시했기 때문에 중복을 제거한 뒤 모든 경우를 소수 판별했다. 0과 1은 소수가 아니므로 예외처리를 해주고 그 외의 경우에는 1, 자기자신을 제외한 수로 모두 나눠보며 체크했다.

프로그래머스 내에서는 통과되었는데 분명 시간초과가 날 여지가 있다고 생각하여 소수판별 알고리즘을 한번 더 정리해보려 한다. 블로그에 이미 올려둔 내용이긴 하지만... 또 까먹었기 때문에 한번 더 정리

# 2022-07-22
# 프로그래머스 Lv2 - 소수 찾기
# https://school.programmers.co.kr/learn/courses/30/lessons/42839
# 소요시간 : 15:10 ~ 15:25 (15m)

from itertools import permutations

# 소수판별 알고리즘
def checkPrimeNum(num):
    if num == 0 or num == 1:
        return False

    for i in range(2, num):
        if num % i == 0:
            return False
    return True


def solution(numbers):
    answer = 0
    num_arr = []
    for num in numbers:
        num_arr.append(num)

    every_case = []
    for i in range(1, len(num_arr) + 1):
        case = list(permutations(num_arr, i))
        for arr in case:
            every_case.append(int("".join(arr)))

    every_case = list(set(every_case))

    for case in every_case:
        if checkPrimeNum(case):
            answer += 1

    return answer

소수 판별 알고리즘

단일 숫자 판별 시

약수의 성질을 살펴보면 모든 약수는 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룬다. 

16의 약수는 1, 2, 4, 8, 16 인데 2x8 = 16, 8x2=16이다.

따라서 특정한 자연수의 모든 약수를 찾을 때 가운데 약수(제곱근)까지만 확인해주면 된다. 

# 소수 판별 (개선된 알고리즘)
import math

def isPrimeNumber(num):
    # 2부터 num의 제곱근까지의 모든 수를 확인하기
    # 제곱근을 구하는 방법은 math.sqrt() 사용. 반환형은 float
    # 음수의 제곱근을 구하게 되면 error 발생하니 유의
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            return False
    return True

대량의 숫자 판별 시 (에라토스테네스의 체)

이 문제에서는 각각의 경우가 소수인지 판단해야 되서 아니지만, 만약 특정 범위까지의 자연수 중 소수가 몇개인지처럼 대량의 소수를 한꺼번에 판별하고자 할 때 사용하면 좋은 방법을 추가로 정리한다.

에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당, 그 인덱스에 해당하는 값을 넣어준다. 2부터 시작하여 특정 숫자의 배수에 해당하는 숫자를 모두 지운다. (자기 자신은 지우지 않음) 

n = int(input())

eratos = [True] * (n+1)
m = int(n**0.5) // math.sqrt 사용해도 ok

for i in range(2, m+1):
	if eratos[i] == True:
    	for j in range(i+i, n+1, i): #i의 배수를 모두 삭제, 본인은 제외
        	eratos[j] = False
            
print([i for i in range(2, n+1) if a[i] == True])