세무민의 알고가자 : 프로그래머스 소수 찾기 문제 풀기

오늘 풀 문제는 소수 찾기!

문제는 쉽다고 생각했는데 생각보다 접근하고 코드 짜는데 오래 걸렸던 문제!

---

문제 설명 & 제한 사항

---

입출력 예시

---

풀이

일단 이번 문제는 코드 구현은 조금 어려웠으나 문제 푸는 방식은 쉽게 생각이 들었다.

예를 들어서 "011" 으로 문제를 풀어본다면 

011라는 문자열을 쪼개서 가능한 숫자를 만든 후 소수인지 판별하면 된다.

	numbers	numbers로 만들 수 있는 수
list	011	0, 1, 1, 01, 11, 10, 01,  011, 101, 110
set	011	0, 1, 01, 11, 10, 011, 101, 110

위의 표처럼 011로 조합할 수 있는 수를 모두 만들어 준 후

SET로 중복값을 제거하면 조합하는 숫자를 모두 확인 가능하다.

즉! 이번 문제를 푸는 방법은

1. numbers의 숫자 조합(순열)을 찾는다.

2. 중복값을 제거해준다.

3. 소수인지 값을 판별해준다. 

4. 소수인지 확인 후 정수 전환 및 마지막 중복값을 제거해준다.

 

---

코드

# while을 이용해서 첫번째로 구현해 본 코드(틀림)

import math
def solution(numbers):
    number = list(numbers)
    result = []
    
    checkList = True
    count = 1
	# 1번 숫자 조합을 만들어 준다.
	while count <= len(number):

        if checkList == False:
            tmp = number[0]
            number = number[1:]
            number.append(tmp)
            count += 1
            checkList = True
        else:
            for j in range(1,len(number)+1):
                result.append(''.join(number[:j]))

            checkList = False
            
	# 2번 list -> set 중복값 제거 
	result = list(set(result))
    answer = []
    
    # 3번 소수 판별하기 -> 제곱근을 이용해서 판별하기 
    for i in range(len(result)):
        checkPoint = 0
        if int(result[i]) == 0 or int(result[i]) == 1:
            continue
        else:
            squrts = int(math.sqrt(int(result[i])))
            for j in range(2, squrts + 1):
                if int(result[i]) % j == 0:
                    checkPoint += 1

            if checkPoint == 0:
                answer.append(result[i])

    # 4번 문자 -> 정수로 변환해준 후 set으로 중복값 제거 
    # Ex) 011 -> 11
    
    answerText = []
    for i in answer:
        answerText.append(int(i))

    return len(set(answerText))
    

우선 순서대로 구현을 했습니다. 

list -> Set -> 소수판별 -> 정수변환 및 set을 진행했습니다. 

여기서 간단히 설명할 부분은 소수 판별 부분이네요

소수 판별 방식은 다양합니다.

그 중에서 소수 판별 시 제가 사용한 방법은 제곱근을 이용했습니다.

우선 0과 1은 소수가 아니라는건 모두들 알고 있으시죠?

그렇다면 2부터 판별이 들어가게 됩니다.

예시로 한번 보면 

소수라는건 결국 자기 자신으로만 나눠지는 값이죠?

그렇다면  나눴을 때 나누어 떨어진다면 결국 소수가 아니라는 의미를 가지죠 

180을 2로 나눴을 때 90으로 나눠 떨어지죠?

그리고 180을 13으로  15로 나눠도 나눠 떨어지죠? 

결국에 어떤 한가지 값이라도 나누어 떨어지게 된다면 소수가 아니겠죠?

또한 단순하게 생각했을 때 제곱근을 사용하게 되면 반복문의 횟수도 줄일 수 있습니다.

81 -> 9 * 9 -> 9으로 81번 확인해야 하는 횟수를 9번으로 축소 시킬 수 있습니다.

어떻게 보면 약수의 개념과 비슷하게 이용할 수 있는거라는 생각도 들었답니다. 

무튼 위의 코드를 돌렸더니...

처참한 결과를 얻을 수 있었습니다.

이 결과를 고민해보면서 느낀 점은 While문이 틀릴 가능성이 크다라는 생각이 들었습니다.

말 그대로 1번을 구현하려면 가능한 숫자를 하나씩 만들어줘야 하는데 

iterator를 생각못한 저의 실수로 while문으로 삽질을 해버렸죠 ㅋㅋㅋ

그래서 순열에 대한 정보를 찾기 시작했습니다. 

좋은 정보가 존재해서 공유를 하면

 

순열에 대해서 itertools.permutation을 이용하면 순열을 쉽게 만들 수 있다고 하네요 ㅎㅎ

그래서 바로 실천해봤습니다.

# 두번째 코드 itertools.permutations이용!

from itertools import permutations
import math
def solution(numbers):
    number = list(numbers)
    numberResult = []
    lenSize = len(numbers)
    result = []
    
    for i in range(len(number)):
        numberResult.extend(list(map(''.join, permutations(number, lenSize - i))))
    
    result = list(set(numberResult))
    
    answer = []
    for i in range(len(result)):
        checkPoint = 0
        if int(result[i]) == 0 or int(result[i]) == 1:
            continue
        else:
            squrts = int(math.sqrt(int(result[i])))
            for j in range(2, squrts + 1):
                if int(result[i]) % j == 0:
                    checkPoint += 1

            if checkPoint == 0:
                answer.append(result[i])

    answerText = []
    for i in answer:
        answerText.append(int(i))

    return len(set(answerText))

while문처럼 거창하게 작성안하고 

list(map)과 permutations면 끝입니다!

while문으로 작성했을 땐 통과를 못했지만 

permutations를 이용하니 쉽게 통과했습니다. 

오늘도 이렇게 하나의 정보를 알아갈 수 있어서 너무 좋네요 ㅋㅋㅋㅋ

---

다음에도 더 좋은 포스팅으로 찾아 오겠습니다.