[완전탐색] 소수 찾기 (프로그래머스, Level 2)

Soorim Yoon·2022년 10월 1일

완전탐색 코테 프로그래머스

알고리즘 & 코딩테스트

목록 보기

34/67

문제

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

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

코드

💡 정답 (오류 해결)

from itertools import permutations
def solution(numbers):
    answer = 0
    
    perms = []
    for i in range(1, len(numbers)+1):
        for n in permutations(numbers, i):     # number 문자열의 각 자리 숫자들의 순열을 생성해 perms 배열에 삽입함
            p = ''.join(n)
            p = int(p)
            if p not in perms:
                perms.append(p)

        # perms = [''.join(n) for n in permutations(numbers)]
        # 위 for문을 위와 같이 한 줄로 작성 가능
    
    for p in perms:
        div = 0     # 나머지가 0인 경우 (나눠 떨어지는 경우의 개수를 카운팅)
        for j in range(2, p):
            if p % j == 0:      # 나눠 떨어지면 (처음에 오류가 발생했던 원인 => 여기서 나눠떨어지는 경우가 발생하면 바로 소수가 아닌 것으로 판별해야 연산량이 크게 줄어듦)
                div += 1
                break
        if div == 0 and p != 0 and p != 1:       
            # 2부터 자기자신-1의 숫자까지 나눠떨어지는 숫자가 없으면 (=소수이면) 정답 변수를 1 증가시킴
            # 0과 1은 소수가 아니므로 p가 해당 숫자는 제외
            answer += 1
    return answer

실행 결과

소수를 판별하는 과정에서 현재 값을 2부터 (자기자신-1)의 값까지 나누며 나눠떨어지는 경우가 있다면, 바로 소수가 아님을 인식하고 다음 과정으로 넘어가도록 했다.

처음에는 나눠떨어지지 않는 값들을 모두 count해서 해당 경우가 0인 경우에만 소수라고 판단했다. 이 과정에서 이미 소수가 아님이 판단되었음에도 (div 값이 1이라도 증가된 경우) 계속 나머지 연산을 진행해 시간 초과 오류가 발생했었다.

오류 해결
if p % j == 0:
   div += 1
   break
div 값이 1 증가한 순간 break문을 통해 다음 연산으로 넘어가도록 함으로써 연산 시간을 단축시켰다.

오답 (시간 초과)

from itertools import permutations
def solution(numbers):
    answer = 0
    
    perms = []
    
    for i in range(1, len(numbers)+1):
        for n in permutations(numbers, i):     # number 문자열의 각 자리 숫자들의 순열을 생성해 perms 배열에 삽입함
            p = ''.join(n)
            p = int(p)
            if p not in perms:
                perms.append(p)

        # perms = [''.join(n) for n in permutations(numbers)]
        # 위 for문을 위와 같이 한 줄로 작성 가능
    
    for p in perms:
        div = 0     # 나머지가 0인 경우 (나눠 떨어지는 경우의 개수를 카운팅)
        for j in range(2, p):
            if p % j == 0:      # 나눠 떨어지면
                # print(p, j)
                div += 1
        if div == 0 and p != 0 and p != 1:       
            # 2부터 자기자신-1의 숫자까지 나눠떨어지는 숫자가 없으면 (=소수이면) 정답 변수를 1 증가시킴
            # 0과 1은 소수가 아니므로 p가 해당 숫자는 제외
            answer += 1
    return answer

실행 결과

시간 초과 에러를 해결하는 방법으로 다시 구현할 예정이다.

순열에 사용되는 숫자의 개수를 바꿔가면서 값을 생성하는 과정에서, 중복되는 값이 perms 배열에 이미 있는 경우 배열에 추가하지 않는 형식으로 진행했다. 이 과정에서 반복되는 숫자는 생성하지 않는 방법이 있지 않을까 생각된다.

위의 이유가 시간 초과 문제의 발생 원인이 아니었다.