프로그래머스 42839 - 소수 찾기 (Lv.5)

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

// 프로그래머스 42839 - 소수 찾기 (Lv.5)
// https://school.programmers.co.kr/learn/courses/30/lessons/42839

// 문제 설명
// 한 자리 숫자가 적힌 종이 조각이 흩어져 있다. 조각을 붙여 만들 수 있는
// 소수가 몇 개인지 구하라. 조각은 한 번씩만 쓸 수 있고 일부만 써도 된다.
// "011"이면 [11, 101] 두 개의 소수를 만들 수 있다(011과 11은 같은 수로 취급).

// 제약 조건
// 1 <= numbers 길이 <= 7
// numbers는 '0'~'9' 문자로만 구성된다.
// 011과 11은 같은 수로 본다.

// Example
// Input : "17"    Output: 3   ([7, 17, 71] — 1은 소수가 아님)
// Input : "011"   Output: 2   ([11, 101])

// 접근 — 부분 순열 완전 탐색(백트래킹) + set 중복 제거 + 시행 나눗셈 소수 판정
// 길이가 최대 7이라 만들 수 있는 수의 개수는 P(7,1)+...+P(7,7) = 13,699개뿐이다.
// 상한이 완전 탐색을 허가하므로 가지치기 없이 전부 만들고 걸러낸다.
// 1) visited[i]로 쓴 조각을 표시하며 DFS. 자리 하나를 붙일 때마다 그 시점의 수를
//    후보로 등록한다(길이 1~n 부분 순열이 한 번의 탐색으로 전부 나온다).
// 2) stoi로 정수화하면 "011" -> 11로 선행 0이 자동 정규화되고, set에 넣으면
//    같은 수가 겹쳐 들어오는 경우까지 사라진다. "011과 11은 같다" 규칙이 코드에서 소멸.
// 3) 후보마다 i*i <= n 시행 나눗셈으로 소수 판정. 최대값 7,654,321의 제곱근은 약 2,767.
// 시간 O(n! * n) 생성 + O(후보 수 * sqrt(최댓값)) 판정, 공간 O(후보 수)
// (n <= 7이므로 생성 13,699개 x 판정 2,767회 = 최악 4천만 미만 — 여유)

#include <string>
#include <vector>
#include <set>

using namespace std;

string paper;                                      // 입력 종이 조각
int visited[8];                                    // 조각 사용 여부 (bool 대신 int)
set<int> cand;                                     // 만들 수 있는 서로 다른 수

bool isPrime(int n)
{
    if (n < 2) return false;                       // 0, 1은 소수가 아니다

    for (int i = 2; i * i <= n; i++)               // sqrt 대신 i*i — 부동소수점 오차 회피
        if (n % i == 0) return false;

    return true;
}

void dfs(string cur)
{
    if (cur.size()) cand.insert(stoi(cur));        // 붙일 때마다 등록 = 부분 순열 전부

    for (int i = 0; i < paper.size(); i++)
    {
        if (visited[i]) continue;

        visited[i] = 1;                            // 넣고
        dfs(cur + paper[i]);
        visited[i] = 0;                            // 빼고
    }
}

int solution(string numbers)
{
    paper = numbers;
    cand.clear();
    dfs("");

    int ret = 0;
    for (int n : cand)
        if (isPrime(n)) ret++;

    return ret;
}

정리

• 커리큘럼 104번. 제약이 곧 풀이 선택인 문제다. 길이 상한 7이면 만들 수 있는 수는 P(7,1)+…+P(7,7) = 13,699개로, 전부 만들고 전부 판정해도 여유가 크다. 상한이 15만 되어도 순열이 1조를 넘어 다른 접근이 필요해지므로, “완전 탐색이 통하는가”를 상한으로 먼저 계산하고 통하면 그대로 가는 게 맞다.
• 순열 문제지만 next_permutation으로는 깔끔하지 않다. 이 문제는 조각을 일부만 써도 되므로 길이가 가변이고, 같은 숫자가 여러 장 있을 수 있어("011") 값 기준 순열은 필요한 경우를 건너뛴다. next_permutation은 배열 전체를 쓰는 고정 길이 순열에 맞고, 부분 순열은 visited 배열 백트래킹이 정석이다. “길이가 가변인가”가 두 도구를 가르는 판단축.
• 재귀 골격의 핵심은 종료 조건이 없다는 점이다. if (cur.size()) cand.insert(...)처럼 자리를 붙일 때마다 후보로 등록하면 길이 1짜리부터 전체 길이까지가 한 번의 DFS로 모두 나온다. “완성됐을 때만 등록”하는 N과 M 계열 골격과 달라, 부분 선택을 허용하는 문제는 등록 위치를 함수 진입부로 올린다.
• "011과 11은 같은 수"라는 규칙에 대응하는 코드가 한 줄도 없다. stoi("011")이 11을 돌려주며 선행 0을 정규화하고, set<int>가 겹치는 값을 흡수한다. 규칙을 조건문으로 옮기려 하면 분기가 늘어나는데, 자료형과 자료구조 선택이 규칙을 대신 처리하게 두는 편이 짧고 안전하다.
• 소수 판정은 i * i <= n 시행 나눗셈. i <= sqrt(n)은 부동소수점 오차가 경계에서 문제를 일으킬 수 있고, 후보 최댓값 7,654,321의 i * i는 int 범위(약 21억) 안이라 오버플로도 없다. if (n < 2) return false를 앞에 두는 게 "17"의 답이 4가 아니라 3인 이유 — 1은 소수가 아니다가 이 문제의 대표 실수 지점.
• 에라토스테네스의 체(상한 7,654,321)로 미리 소수 표를 만드는 대안도 있지만, 후보가 최대 13,699개뿐이라 8MB 배열을 채우는 비용이 판정 비용보다 크다. 체는 “판정 횟수가 구간 크기에 비례할 때” 이득이고, 여기처럼 드문 조회면 시행 나눗셈이 낫다. 실측으로도 최악 입력 "1234567"이 10ms 미만.
• 검증: 예제 2개(3, 2)와 경계 케이스 — "1"(→ 0), "7"(→ 1), "0"(→ 0), 중복 숫자 "44"(→ 0), 소수 없는 "9999999"(→ 0), 최악 길이 "1234567"(→ 1336, 10ms 미만) 통과. 추가로 후보 생성을 비트마스크 + next_permutation으로, 판정을 O(n) 나눗셈으로 따로 구현해 "1234"의 답 14를 독립 대조 (MSVC /std:c++17 /O2 컴파일·실행).

핵심 요약 — 길이 상한 7 → 부분 순열 13,699개라 완전 탐색이 그대로 통한다. 길이가 가변인 부분 순열은 next_permutation이 아니라 visited 백트래킹이고, 등록을 함수 진입부에 두면 모든 길이가 한 번의 DFS로 나온다. stoi + set이 “011 = 11” 규칙을 코드 없이 처리하며, 소수 판정은 i * i <= n과 n < 2 가드가 전부.