[프로그래머스] 소수 찾기 - LV.2

지히·2022년 7월 12일
0

알고리즘

목록 보기
7/8

📑 문제 주소

https://school.programmers.co.kr/learn/courses/30/lessons/42839?language=python3


🔥 문제 설명

주어진 문자열의 숫자들을 통해 숫자를 만들고, 그 중에서 소수의 갯수를 return 하는 문제이다.


🔥 나의 풀이

이것저것 마음에 안드는 부분이 많지만 무엇보다 반복문을 5번 사용하는 아주 효율성이 똥인 코드이다. 효율성 체크가 없어 통과할 수 있었다. itertools의 permutations(순열)을 사용하여 풀었다. 구체적인 로직은 다음과 같다.

먼저 문자열로 주어진 숫자배열을 하나하나 잘라서 str_num배열을 만들어준다. 그리고 permutations로 순열을 만들어주는데 여기서 두번째 인자는 해당 순열에서 몇개를 뽑아 순열을 만들지를 나타낸다. 우리는 1~N개의 순열이 전부 필요하므로 for문을 돌면서 두번째 인자를 하나씩 증가하며 모든 길이의 순열을 만들도록 한다. 이 과정을 거치면 (첫번째 테스트 케이스 ===>) (1) (7) (1,7) (7,1)이 된다.

만들어진 순열들은 tuple 형태에서 int형태로 변환하여 미리 만들어놓은 집합에 넣는다.(set은 중복처리를 알아서 해줌) 이때 우리의 목적은 소수를 찾는것이기 때문에 소수와 상관이 없는 0과 1은 추가하지 않는다.

이제 마지막으로 소수를 찾는 과정이다. 앞의 집합만큼의 반복문을 돌며 2~(N-1)까지 나머지가 0인것을 찾는다. 이때 set은 인덱싱이 불가능한 자료형이다. 따라서 하나씩 pop()하여 소수를 찾는다.

from itertools import permutations
def solution(numbers):
    answer = 0
    numbers_length = len(numbers)
    str_num = [numbers[i] for i in range(numbers_length)]
    check = set()
    for i in range(1,numbers_length+1):
        data = permutations(str_num,i)
        int_str = ''
        for j in data:
            int_str = ''.join(j)
            if int(int_str)>=2:
                check.add(int(int_str))
    minus = len(check)
    for i in range(len(check)):
        pop_int = check.pop()
        for j in range(2,pop_int):
            if pop_int%j ==0:
                answer +=1
                break
    return minus-answer


✅ 다른 사람의 풀이

비슷한 코드도 있고, 정말 다른 풀이도 존재하였다. 순열을 사용한 비슷한 코드라도 그 안에서 조금씩 순서라던지 사용한 함수들이 다른것을 알 수 있었다. 그 중 프로그래머스에서 가장 좋아요를 많이 받은 코드를 가져왔다.(왜 좋아요를 가장 많이 받았는지 알겠다...)

from itertools import permutations
def solution(n):
    a = set()
    for i in range(len(n)):
        a |= set(map(int, map("".join, permutations(list(n), i + 1))))
    a -= set(range(0, 2))
    for i in range(2, int(max(a) ** 0.5) + 1):
        a -= set(range(i * 2, max(a) + 1, i))
    return len(a)

📍 map 함수
map(첫번째 인자, 두번째 인자)형식으로 사용된다.
첫번째 인자는 int(), join()등의 적용하고 싶은 함수가 들어간다.
두번째 인자는 반복 가능한 자료형 list등이 들어간다.
두번째 인자의 값을 하나씩 뽑아, 첫번째 인자의 함수에 집어넣어 함수를 수행한다.
return값은 map객체를 반환한다.

처음보는 연산자나 내가 잘 쓰지 않는 함수들이 보여 하나씩 살펴보겠다.
먼저 이 코드도 순열을 사용한다. 내 풀이와 같이 for문을 돌며 두번째 인자를 하나씩 증가하며 순열을 생성하는데 나는 직접 문자열을 하나씩 분리하여 하였지만 분리하지 않아도 생성되는것을 확인하였다... 생성된 순열 자료형을 map함수를 사용하여 모든 항목에 대해 join함수로 붙여서 string을 만들어준다.
이를 다시한번 map함수를 사용하여 전부 int로 바꾼뒤, 미리 만들어 놓은 a 집합에 추가하는데 여기서 처음보는 |= 연산자가 사용된다. |연산자는 숫자에서 보면 비트 연산자 이지만, set이나 dictonary등의 자료형에서 보면 합집합을 나타낸다. 따라서 위 코드는 각자 set을 만들고 이를 전역 set()인 a에 하나씩 합집합 연산을 하는 것임을 알 수 있다. 이렇게 되면 a라는 set은 중복되지 않는 소수를 갖게 된다.
이러한 방식으로 위 코드는 a에 소수인 값만 남겨 그 길이를 return하는 방식으로 진행된다.

profile
알고리즘 천재가 될꺼야:)

0개의 댓글