프로그래머스 등급2 - 소수 찾기

소수 찾기 문제 바로 가기

풀이 날짜: 2026-05-12

baekjoon 알고리즘 문제 풀이

풀이 코드


def solution(numbers):
    answer = 0
    made = set()
    
    def is_prime(data):
        if data < 2:
            return False
        for i in range(2,int(data**0.5)+1):
            if data % i == 0:
                return False
        return True        
    
    def dfs(now,remain):
        nonlocal answer
        
        if now != "":
            number = int(now)
            
            if number not in made:
                made.add(number)
                
                if is_prime(number):
                    answer += 1
        
        for i in range(len(remain)):
            dfs(now+remain[i], remain[:i] + remain[i+1:])
    
    dfs("", numbers)
    
    return answer

문제 핵심

제의 핵심은 주어진 숫자 문자열에서 만들 수 있는 모든 숫자 조합을 직접 생성해보고, 그 숫자가 소수인지 하나씩 판별하는 것이다. 단순히 한 번의 계산으로 답을 구하는 문제가 아니라, 가능한 모든 경우를 탐색해야 하기 때문에 완전탐색 성격이 강하다. 다만 실제 구현 방식은 DFS(깊이 우선 탐색)와 백트래킹 구조를 활용하게 된다.

접근 방법 (아이디어)

처음에는 문자열을 하나씩 보면서 바로 소수 판별을 하려고 접근했지만, 이 문제는 먼저 “숫자 조합 생성” 과정이 반드시 필요하다는 점이 핵심이었다. 예를 들어 “17” 이라는 입력이 들어오면 단순히 1, 7만 검사하는 것이 아니라, “17”, “71” 같은 조합도 모두 만들어야 한다. 따라서 현재까지 만든 숫자와 아직 사용하지 않은 숫자를 함께 관리하며 모든 경우를 재귀적으로 탐색하는 방식으로 접근했다.

DFS + 백트래킹 구조

이 문제의 핵심 구현은 DFS 함수였다. 현재까지 만든 숫자를 now, 아직 사용하지 않은 숫자를 remain으로 두고 재귀적으로 탐색했다.

dfs(now + remain[i], remain[:i] + remain[i+1:])

현재 숫자 뒤에 새로운 숫자를 하나 붙이고, 사용한 숫자는 남은 문자열에서 제거한 뒤 다시 DFS를 호출하는 구조이다. 이를 통해 모든 순열 조합을 직접 생성할 수 있었다.

소수 판별 최적화

숫자를 생성한 뒤에는 소수 여부를 판별해야 했다. 처음에는 단순히 2부터 num-1까지 전부 나누는 방식도 생각했지만, 이는 비효율적이었다. 따라서 제곱근까지만 검사하는 방식으로 최적화했다.

for i in range(2, int(num ** 0.5) + 1):

약수는 항상 짝으로 존재하기 때문에, √N 이하에서 약수를 찾지 못하면 그 이후에도 존재하지 않는다는 원리를 활용한 것이다. 이를 통해 불필요한 반복을 크게 줄일 수 있었다.

중복 처리

입력값에 “011” 처럼 같은 숫자가 포함된 경우에는 동일한 숫자가 여러 번 생성될 수 있었다. 예를 들어 “011” 에서는 “11” 이 여러 번 만들어질 수 있기 때문에, 중복 처리가 필요했다. 이를 위해 set()을 사용하여 이미 검사한 숫자인지 확인한 뒤 소수 판별을 수행했다.

이번 문제를 통해 느낀 점

이번 문제를 통해 완전탐색 문제는 단순 반복문만으로 해결하는 것이 아니라, DFS와 백트래킹 구조를 통해 “가능한 모든 경우를 직접 생성하는 사고”가 중요하다는 점을 느꼈다. 특히 remain[:i] + remain[i+1:] 구조를 활용해 사용한 숫자를 제거하며 탐색하는 방식이 인상적이었다. 또한 소수 판별 최적화와 중복 제거까지 함께 고려해야 했기 때문에, 단순 구현 문제보다 훨씬 사고력이 필요한 문제라는 것을 체감할 수 있었다.

Vienna sausage