[Algorithm: 완전탐색] 프로그래머스 <소수찾기>

문제

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

프로그래머스

 

문제 설명

1 ~ 7자리의 숫자가 문자열 형태로 주어진다. 이 숫자들을 조합하여 만들 수 있는 모든 숫자 중 소수의 개수를 구하는 문제이다.

소수란 1과 자기 자신만을 약수로 가지는 수를 의미한다.

 

예를 들어 "17"이 주어졌다면 만들 수 있는 숫자는 다음과 같다.

1, 7, 17, 71

 

이 중 소수는 7, 17, 71이므로 정답은 3이다.

 

 

처음 접근과 고민

문제를 보고 크게 두 가지 로직이 필요하다고 판단했다.

1. 소수를 판별하는 로직
2. 주어진 숫자를 조합하는 로직

 

1. 소수 판별 로직

소수는 1과 자기 자신만 약수로 가지는 수이다.

따라서 어떤 수 n이 있을 때 2부터 n-1까지 순회하면서 나누어 떨어지는 수가 있다면 소수가 아니다.

 

이 방식으로 소수를 판단할 수 있다.

 

예를 들어 17이라면

17 % 2
17 % 3
17 % 4
...

 

이렇게 확인했을 때 나누어 떨어지는 수가 없다면 소수이다.

 

2. 숫자 조합 로직

이 문제가 핵심이었다.

예를 들어 "17"이라는 숫자가 주어졌다면 단순히

1, 7 만 보는 것이 아니라

1
7
17
71

 

이렇게 숫자의 순서까지 고려한 모든 경우를 확인해야 한다.

 

즉 순열 형태의 탐색이 필요하다.

 

처음에는 단순 반복문으로 해결하려고 했지만 숫자의 길이가 최대 7자리이기 때문에 다음과 같은 문제가 발생했다.

1자리 숫자
2자리 숫자
3자리 숫자
...
7자리 숫자

 

모든 경우를 반복문으로 작성하려면 7중 반복문이 필요하다. 이는 현실적으로 구현하기 어려운 구조이다.

그래서 DFS를 활용하여 모든 경우의 수를 탐색하기로 했다.

 

DFS를 사용한 이유

DFS는 하나의 선택을 하고, 그 선택을 기반으로 계속 탐색을 확장하는 방식이다.

예를 들어 "173"이라는 숫자가 주어졌다면 탐색 과정은 다음과 같이 진행된다.

 

├─ "1"
│  ├─ "17"
│  │  └─ "173"
│  └─ "13"
│     └─ "137"
├─ "7"
│  ├─ "71"
│  └─ "73"
└─ "3"
   ├─ "31"
   └─ "37"

이처럼 DFS를 이용하면 모든 숫자 조합을 자연스럽게 생성할 수 있다.

 

 

 

추가로 고려해야 했던 문제

숫자가 "11"과 같이 중복된 숫자일 경우 동일한 숫자가 여러 번 생성될 수 있다.

 

예를 들어 "11"의 경우

1
11
1
11

 

위와 같은 숫자가 여러 번 만들어진다.

따라서 중복 제거를 위해 Set 자료구조를 사용했다.

---

 

문제 풀이

Set 선언

Set<Integer> set = new HashSet<>();

 

중복된 숫자를 제거하기 위해 HashSet을 사용한다.

 

solution 함수

public int solution(String numbers) {
    boolean[] visited = new boolean[numbers.length()];

    dfs("", numbers, visited);

    return set.size();
}

각 숫자를 한 번씩만 사용하기 위해 visited 배열을 선언한다. DFS 탐색이 끝난 후 set에 저장된 소수의 개수를 반환한다.

 

소수 판별 함수

private boolean isPrime(int number) {
    if (number == 1 || number == 0) {
        return false;
    }
    
    for (int i = 2; i < number; i++) {
        if (number % i == 0) {
            return false;
        }
    }
    
    return true;
}

0과 1은 소수가 아니므로 예외 처리한다.

그 이후에는 2부터 number-1까지 순회하면서 나누어 떨어지는 값이 있는지 확인한다.

 

DFS 구현

private void dfs(String current, String numbers, boolean[] visited) {        
    if (!current.equals("")) {
        int num = Integer.parseInt(current);
        if (isPrime(num)) {
            set.add(num);
        }
    }
    
    for (int i = 0; i < numbers.length(); i++) {
        if (visited[i]) continue;

        visited[i] = true;
        dfs(current + numbers.charAt(i), numbers, visited);
        visited[i] = false;
    }
}

 

DFS는 다음과 같은 방식으로 동작한다.

1. 현재까지 만든 숫자가 존재하면
  → 정수로 변환
  → 소수 여부를 판단한다.

2. numbers를 순회하면서 아직 사용하지 않은 숫자를 선택한다.

3. 선택한 숫자를 current 뒤에 붙여 새로운 숫자를 만든다.

4. DFS를 재귀적으로 호출한다.

5. 탐색이 끝나면 visited 값을 다시 false로 되돌린다.

이 과정을 백트래킹이라고 한다.

 

---

 

최종 코드

import java.util.*;

class Solution {
    Set<Integer> set = new HashSet<>();
    
    public int solution(String numbers) {
        boolean[] visited = new boolean[numbers.length()];
        
        dfs("", numbers, visited);
        
        return set.size();
    }
    
    private void dfs(String current, String numbers, boolean[] visited) {        
        if (!current.equals("")) {
            int num = Integer.parseInt(current);
            if (isPrime(num)) {
                set.add(num);
            }
        }
        
        for (int i = 0; i < numbers.length(); i++) {
            if (visited[i]) continue;

            visited[i] = true;
            dfs(current + numbers.charAt(i), numbers, visited);
            visited[i] = false;
        }
    }
    
    private boolean isPrime(int number) {
        if (number == 1 || number == 0) {
            return false;
        }
        
        for (int i = 2; i < number; i++) {
            if (number % i == 0) {
                return false;
            }
        }
        
        return true;
    }
}

 

---

 

 

시행착오

처음에는 DFS 알고리즘 자체가 익숙하지 않아 구현 과정에서 여러 번 막혔다.

특히 다음 부분에서 어려움을 겪었다.

1. DFS 파라미터 설계

처음에는 char 단위로 처리하려 했지만 숫자를 이어 붙여야 하기 때문에 String 형태로 관리하는 것이 더 적절했다.

 

2. 방문 배열의 필요성

처음에는 단순히 숫자를 붙이는 방식으로 구현하려 했지만 이미 사용한 숫자를 다시 사용할 수 있는 문제가 발생했다.

이를 해결하기 위해 visited 배열을 활용했다.

 

3. 중복 숫자 문제

"11"과 같이 같은 숫자가 있을 경우 동일한 숫자가 여러 번 생성된다. 이 문제를 해결하기 위해 HashSet을 활용하여 중복을 제거했다.

 

정리

이 문제는 단순한 소수 판별 문제가 아니라 DFS를 활용한 완전탐색 + 순열 생성 + 중복 제거(Set)

세 가지 개념이 함께 사용되는 문제였다.

 

특히 DFS + 백트래킹 구조를 이해하는 데 좋은 문제였으며 순열 기반 탐색 문제를 해결하는 기본적인 패턴을 익힐 수 있었다.

 

배운 점

• DFS는 선택 → 재귀 → 복구(백트래킹) 구조로 동작한다.
• 순열이나 조합 문제에서는 DFS가 매우 유용하다.
• 중복 가능성이 있는 문제에서는 Set을 활용하는 것이 효과적이다.