[프로그래머스] 소수 찾기 (Lv. 2 JavaScript)

📝 문제 설명

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

프로그래머스

목표: 한 자리 숫자가 적힌 종이들이 주어졌을 때(문자열 numbers) 이 한자리 수들로 만들 수 있는 소수가 몇 개인지 반환해야한다.

핵심 조건:

• numbers는 “17” 이러한 형태로 주어지며, 이는 숫자 ‘1’, ‘7’ 으로 봐야한다.
• numbers의 길이는 1이상 7이하의 문자열. 즉, 한자리 숫자가 1~7개 주어진다.
• numbers는 0~9까지 숫자로만 이루어져있다.

---

🔍 풀이 과정 (나만의 풀이 전략)

이 문제는 총 두 단계로 구성된다.

1. 주어진 numbers로 만들 수 있는 숫자 조합을 먼저 파악
2. 이게 소수인지 판별하는 방식으로 구현하고자 한다.

주어진 numbers의에서 만들 수 있는 모든 자리 수 (1 ~ N자리)를 구해야 하므로, DFS 알고리즘을 사용한다.

숫자들을 하나씩 붙여가면서 가장 깊은 자릿수에 방문하면 이전으로 백트래킹한 후 다시 다른 조각들을 이어붙이는 수직적인 탐색 방식의 DFS를 통해 구현한다.

DFS 구현을 위해 이미 방문한 숫자는 다음 탐색에서 제외해야 하므로 visited 배열을 통해 방문 체크를 한다.

다음과 같은 흐름으로 탐색을 진행한다.

[0층] "" (시작)
  │
  ├── [1층] "1"  ─── [2층] "17" ─── [3층] "173" (➡️ 복귀)
  │                    │
  │                    └── [2층] "1"로 복귀 후 다음 조각 '3' 선택 ➡️ [2층] "13" ─── [3층] "137" (➡️ 복귀)
  │
  ├── [1층] "1" 갈래 완전 종료 후 ""로 복귀 ➡️ 다음 조각 '7' 선택 ➡️ [1층] "7" ... (반복)

    const permutation = (current, depth) => {
        if (depth > 0) set.add(parseInt(current));
        if (depth === arr.length) return;
        
        for (let i=0; i < arr.length; i++) {
            if (visited[i] === false) {
                visited[i] = true;
                permutation(current + arr[i], depth + 1);
                visited[i] = false;
            }
            
        }
    }
   permutation("", 0);

“173”를 예시로 상세한 실행 흐름을 추적하면 아래 표와 같다.

 

현재 함수	i (루프 인덱스)	visited 상태	set 상태	진행 상황
permutation(’’, 0)	0	[T, F, F]	[]	visited[0] = true 체크 후 permutation(’1’, 1) 호출
permutation(’1’, 1)	0	[T, F, F]	[1]	set에 ‘1’ 추가,
visited[0]이 true 즉, 이미 방문한 상태이므로 다음 인덱스로 넘어감
	1	[T, T, F]	[1]	visited[1] = true 체크 후 permutation(’17’, 2) 호출
permutation(’17’, 2)	0	[T, T, F]	[1, 17]	set에 ‘17’ 추가,
visited[0]이 true 즉, 이미 방문한 상태이므로 다음 인덱스로 넘어감
	1	[T, T, F]	[1, 17]	visited[1]이 true 즉, 이미 방문한 상태이므로 다음 인덱스로 넘어감
	2	[T, T, T]	[1, 17]	visited[2] = true 체크 후 permutation(’173’, 3) 호출
permutation(’173’, 3)	0	[T, T, T]	[1, 17, 173]	set에 ‘173’ 추가,
visited[0]이 true 즉, 이미 방문한 상태이므로 다음 인덱스로 넘어감
	1	[T, T, T]	[1, 17, 173]	visited[1]이 true 즉, 이미 방문한 상태이므로 다음 인덱스로 넘어감
	2	[T, T, T]	[1, 17, 173]	visited[2]이 true 즉, 이미 방문한 상태. 루프 종료 후
permutation(’17’, 2)	2	[T, T, F]	[1, 17, 173]	visited[2] = false로 복구.
루프 종료
permutation(’1’, 1)	1	[T, F, F]	[1, 17, 173]	visited[1] = false복구 후 다음 인덱스로
permutation(’1’, 1)	2	[T, F, T]	[1, 17, 173]	visited[2] = true 체크 후 permutation(’13’, 2) 호출
permutation(’13’, 2)	0	[T, F, T]	[1, 17, 173, 13]	set에 ‘13’ 추가.
visited[0]이 true 즉, 이미 방문한 상태이므로 다음 인덱스로 넘어감
	1	[T, T, T]	[1, 17, 173, 13]	visited[1] = true 체크 후 permutation(’137’, 3) 호출
permutation(’137’, 3)	0~2	[T, T, T]	[1, 17, 173, 13, 137]	set에 ‘137’ 추가.
이후 visited[0~2]가 true 이미 방문한 상태이므로 루프 종료
permutation(’13’, 2)	2	[T, T, F]	[1, 17, 173, 13, 137]	visited[2] = false복구 후 루프 종료
permutation(’1’, 1)	2	[T, F, F]	[1, 17, 173, 13, 137]	visited[1] = false복구 후 루프 종료
permutation(’’, 0)	0	[F, F, F]	[1, 17, 173, 13, 137]	visited[0] = false복구 후 다음 인덱스로
permutation(’’, 0)	1	[F, T, F]	[1, 17, 173, 13, 137]	visited[1] = true 체크 후 permutation(’7’, 1) 호출
permutation(’7’, 1)	0	[T, T, F]	[1, 17, 173, 13, 137, 7]	set에 ‘7’ 추가.
이후
visited[0] = true 체크 후 permutation(’71’, 2) 호출
				… 이후 반복

이 후 소수 판별 함수의 로직은 다음과 같다.

1. number가 1 이하인 경우 제외
2. 2부터 시작해서 주어진 number의 제곱근까지 루프문을 돌면서 i로 나누었을 때 나머지가 존재하지 않는다면. (딱 나누어진다면) 소수가 아니라고 판별한다.

---

💻 코드 (Code)

function isPrime(number) {
    if (number <= 1) return false;
    
    for (let i = 2; i<=Math.sqrt(number); i++) {
        if (number % i === 0) return false;
    }
    return true;
}

function solution(numbers) {
    var answer = 0;
    const set = new Set(); // 만들 수 있는 숫자 조합을 저장할 Set 집합 (중복을 허용 X)
    const arr = numbers.split("") // 숫자의 각 자리를 분해하여 배열로 변환
    const visited = new Array(arr.length).fill(false);
    
    const permutation = (current, depth) => {
        if (depth > 0) set.add(parseInt(current));
        if (depth === arr.length) return;
        
        for (let i=0; i < arr.length; i++) {
            if (visited[i] === false) {
                visited[i] = true;
                permutation(current + arr[i], depth + 1);
                visited[i] = false;
            }
            
        }
    }
    
    permutation("", 0);
    
    set.forEach((num) => {
        if (isPrime(num)) {
            answer++;
        }
    })
    return answer;
}

최적화된 코드

function isPrime(number) {
    if (number <= 1) return false;
    if (number === 2) return true;
    if (number % 2 === 0) return false; // 짝수인 경우 제외
    
    for (let i = 3; i<=Math.sqrt(number); i+=2) {
        if (number % i === 0) return false;
    }
    return true;
}

function solution(numbers) {
    var answer = 0;
    const set = new Set(); // 만들 수 있는 숫자 조합을 저장할 Set 집합 (중복을 허용 X)
    const arr = numbers.split("") // 숫자의 각 자리를 분해하여 배열로 변환
    const visited = new Array(arr.length).fill(false);
    
    const permutation = (current, depth) => {
        if (depth > 0) set.add(parseInt(current));
        if (depth === arr.length) return;
        
        for (let i=0; i < arr.length; i++) {
            if (visited[i] === false) {
                visited[i] = true;
                permutation(current + arr[i], depth + 1);
                visited[i] = false;
            }
            
        }
    }
    
    permutation("", 0);
    
    set.forEach((num) => {
        if (isPrime(num)) {
            answer++;
        }
    })
    return answer;
}

소수 판별 함수에서 짝수인 경우를 제외하면 소수 판별 속도를 더 빠르게 할 수 있다.

---

❓ 꼬리 질문 및 복습 (Self-Q&A)

복습

완전 탐색

완전 탐색은 문제의 해를 찾기 위해 가능한 모든 케이스를 빠짐없이 탐색하는 알고리즘으로

100%의 정답률을 보장하지만, 입력 데이터의 크기에 따라 연산량이 무지막지하게 늘어나는 문제가 존재한다. 따라서 대용량 데이터 처리에는 적합하지 않고 주로 탐색 범위가 좁을 때 최적의 선택이다.

완전 탐색의 종류로는

• 단순 Brute Force: 반복문과 조건문만으로 처음부터 끝까지 다 뒤지는 방식
• 비트마스크(Bitmask): 이진수 비트 연산을 이용해 모든 경우의 수를 표현하고 탐색하는 방식
• 재귀 함수를 이용한 순열/조합: DFS 등을 활용해 모든 가능한 순서를 조합하는 방식
• BFS/DFS: 그래프나 트리 형태의 상태 공간을 탐색하는 방식

완전 탐색의 시간 복잡도는 경우의 수에 따라 O(2^n), O(N!)(순열) 등

이번 문제에서는 주어진 종이 조각의 개수(numbers)가 최대 7개로 제한되었기 때문에 완전 탐색을 사용하는 것이 적합한 문제였다.

DFS (완전 탐색)

DFS는 그래프나 트리 자료구조에서 시작 정점으로부터 연결된 한 갈래를 선택해서 최대한 깊숙히 바닥 노드까지 파고들어 탐색한 뒤, 더 이상 갈 곳이 없으면 내려온 길을 되돌아가 다음 갈래를 선택하는 알고리즘이다. 이는 Call Stack이나 LIFO를 이용해 작동한다.

시간 복잡도는 일반적으로 그래프 탐색 시 정점(V)과 간선(E)를 모두 확인하므로 O(V+E)이다. 이번 문제에서는 조각을 뽑는 가짓수와 순열의 가짓수를 고려해 O(N*N!)의 시간 복잡도를 가진다.

DFS에서 주요 관련 개념이 있는데

• 백트래킹: 해를 찾는 도중에 막힐 경우(바닥 노드에 도달하는 등), 이전 상태로 되돌아가서 다른 경로를 다시 시도하는 알고리즘이다.
• 가지치기(Pruning): 백트래킹 과정에서 이 경로는 더 들어가봤자 어차피 해를 구할 수 없다라고 판단되는 갈래를 미리 차단하여 연산량을 줄이는 최적화 기법이다.

그렇다면 이번 문제에서 DFS를 사용하는 이유는

• permutation("") 으로 시작하면서 빈 문자열에서 조각 하나를 고를 때마다 트리의 아래 depth로 내려간다. “1”에서 “17”이 되는 것은 트리의 자식 노드로 이동하는 셈이다.
• DFS는 Call Stack을 이용해서 내가 지금 어떤 조각들을 거쳐서 이 깊이까지 내려왔는지를 기억한다. “173” 이라는 바닥 노드에 도달했을 때 메모리 스택에는 [”1”, “7”, “3”]이라는 경로가 수직으로 쌓여있다.
• 만약 BFS(넓이 우선)으로 구현하려 했다면, ‘1’고르고 ‘7’ 고르고 ‘3’ 고른 뒤에 다시 위로 올라가서 ‘17’, ‘13’을 고르는 식으로 가로로 움직여야 한다. 이는 이전 층의 상태를 모두 큐에 저장하여야 하므로 메모리 낭비가 심하다. DFS는 한 놈을 끝까지 파고들어 숫자를 완성하고 돌아오는 방식이기 때문에 이번 문제와 같이 순열 조립에 최적화된 형태라고 할 수 있다.

그렇다면 이번 문제를 떠나서 앞으로 어떤 문제를 풀이하려 할 때 아 이 때는 DFS가 적합하다! 라고 판단하는 기준은 어떨까?

1. 모든 경우의 수를 조합하거나 나열해야하는 상황 (순열, 조합, 부분집합)
2. 이전의 선택이 다음의 선택에 영향을 주며 상태가 누적되는 경우
   1. 이번 문제에서 visited 배열을 사용한 것 처럼 과거 선택에 대한 기록을 남기는 경우
3. 가장 먼 곳이나 바닥을 확인해야 결론이 나는 경우
   1. 경로 탐색 문제에서 ‘미로의 출구까지 갈 수 있는가?’, ‘트리의 리프 노드(끝)까지 도달했을 때 총합이 얼마인가?’ 와 같이 중간 과정보다 끝까지 가봐야 정답 조건을 충족하는 경우
4. 제약 조건 N의 크기가 매우 작을 때 (완전 탐색 기반의 경우!)
   1. 완전 탐색 기반의 DFS는 시간 복잡도가 O(2^N) 이나 O(N!)으로 큰 편이다. 간혹 문제에서 N의 조건이 10 이하, 15이하와 같이 범위가 극단적으로 작은 경우 완전 탐색으로 구현하는 문제라는 힌트라고 볼 수 있다.
5. 일반적인 DFS (그래프/트리 탐색)는
   1. "미로가 주어졌을 때 출구까지 갈 수 있는가?"처럼 정해진 지도(그래프)가 이미 존재할 때 사용한다. 이는 중복 방문을 막는 것이 목적으로 따라서 visited[] 를 true에서 false로 탐색이 완전 끝날 때 까지 바꾸지 않는다.
   2. 이는 정점만 훑으면 되므로 N이 비교적 크다. ****(N ≥ 100,000)

꼬리질문

Q. DFS를 재귀 함수(Recursion) 대신 다르게 구현하는 방법이 있나요?

재귀 함수는 기본적으로 컴퓨터 내부의 Call Stack을 사용하는 방식이다. 따라서 개발자가 명시적으로 스택을 선언하고 직접 반복문을 돌리면서 데이터를 Push/Pop 하는 방식으로도 동일하게 DFS를 구현할 수 있다.

Q. 이 문제에서 '백트래킹(Backtracking)'과 'DFS'의 차이점은 무엇인가요?

• DFS는 트리나 그래프의 모든 노드를 빠짐없이 방문하는 탐색 알고리즘 자체를 의미한다.
• 백트래킹은 탐색을 진행하다가 조건을 만족하지 않으면 더 깊이 들어가지 않고 이전 상태로 되돌아가 나오는 알고리즘 설계 패러다임이다.
• 이번 풀이에서 모든 숫자를 다 만들기 때문에 가지치기를 하지는 않았지만, 하나의 조각을 쓰고 난 뒤 복구하는 과정 (visited[i] = false)에 백트래킹의 핵심 메커니즘이 녹아들어 있다.

---

💬 마무리하며

알고리즘 공부를 시작하면서 처음으로 완전 탐색 문제 풀이를 시도해보면서 어려움이 있었던 것 같습니다. 스스로 문제를 해결하려고 고민했을 때 결국 해결책을 찾지 못하고 AI의 도움을 받아 학습하면서 문제를 해결했습니다. 이번 풀이를 통해 DFS 개념에 대해 복습하게 되었고, 여기서는 완전 탐색을 위해 DFS 알고리즘을 활용해보았는데, 이 경험을 통해 앞으로 비슷한 유형에서는 직접 더 빠르게 해결할 수 있으면 좋겠습니다!

파이팅!