[프로그래머스][파이썬/Python] 소수 찾기 - level 2

* 프로그래머스에는 '소수 찾기'라는 문제가 level 1과 level 2에 모두 존재한다. 구분하고자 level 2를 제목에 명시했다.

 

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

제한 조건

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

 

입출력 예

 

제출 코드

from itertools import permutations
def solution(numbers):
    answer = 0

    # 가능한 수의 조합 만들기
    lst = ','.join(numbers).split(',')
    possible = []

    for i in range(len(numbers)):
        possible.extend(list(permutations(lst, i+1)))

    possible = [''.join(i) for i in possible]
    possible = sorted(list(set(map(int, possible))))

    idx = -1
    for i in range(len(possible)):
        if possible[i] <= 1: idx = i
        else: break
            
    if idx == -1: pass
    else: possible = possible[idx+1:]

    # 소수 찾아내기
    for num in possible:
        for i in range(2, round(num ** 0.5) + 1):
            if num % i == 0:
                break
        else:
            answer += 1

    return answer

(1) line 6

입력값이 문자열로 주어지는데, 순열을 만들기 좋은 형태로 리스트를 선언.

※ 제출 후 깨달았는데 이것은 의미 없는 짓. iterable한 문자열이나 리스트나 모두 순열 만들기 가능. 심지어 이것과 관련하여 포스팅을 썼었는데도 또 까먹고 앉아있다. 한심해. 이걸 굳이 안 쓰고 10번 라인에 permutations의 인자값을 lst 대신 numbers로 썼다면 아주 조금의 시간이라도 아낄 수 있을 것이다.

 

(2) line 7

추후 순열을 만들고, 그 순열 중에서 소수인지 판별할 만한 숫자들을 담을 리스트 선언.

 

(3) line 9, 10

문자열 'numbers'의 각 숫자들을 1, 2, 3, ..., len(numbers) 개 이용하여 순열을 순차적으로 만들고 그것들을 리스트 'possible'에 붙인다.

 

(4) line 12

튜플의 형태로 존재하는 각 순열들을 문자열 형태로 변환

 

(5) line 13

   1) 각 순열들을 int형으로 변환 : 앞이 0으로 시작했던 문자열들은 자연스럽게 0이 사라짐

   2) 변환된 값들을 set 형태로 저장 : 중복값을 제거하기 위함

   3) set을 오름차순으로 정렬된 리스트 형태로 변환 : set은 정렬하는 기능이 없기 때문에 리스트 형태로 변환

 

(6) line 15 ~ 21

소수인지 판별할 만한 숫자들이 오름차순으로 정렬되어 있는 리스트 'possible'에서 0, 1이 존재하다면 제거

 

(7) line 24 ~ line 29

소수인지 판별하는 반복문. 핵심은 효율성을 증진시키기 위해 for문의 반복 범위를 round(num ** 0.5) + 1까지 설정해줘야 한다는 것이다. 소수 특성상 소수의 루트값까지만 나눠보고 나눠지는 숫자가 없다면 그 수는 소수이다. 반복 범위를 소수의 루트값 정도까지만 설정해주면 효율성이 매우 좋아진다.

다만, 여기서 궁금한 점이 생겼다. 너무 궁금해서 프로그래머스 질문란에도 올렸다. 25번 줄에서 반복 범위를 round(num ** 0.5) + 2까지로 설정할 경우 많은 테스트 케이스를 실패하는 것이 확인됐는데, 도무지 이해가 가지 않는다. 내 생각으로는 for문이 딱 한 번 더 돌게 되는 거라 효율성이 떨어졌으면 떨어졌지, 갑자기 테스트 케이스를 실패하는 일은 없어야 한다고 생각한다. 대체 왜 그런 것일까..?

 

 

 

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