[99클럽/코딩테스트 챌린지/C++] 소수 찾기 문제 해결 (완전 탐색 + 백트래킹)

문제 링크 : 

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

프로그래머스

문제 요약

이 문제는 주어진 숫자 조각들로 만들 수 있는 모든 숫자 조합 중 소수가 몇 개인지 찾는 것입니다. 문제를 해결하기 위해:

1. 숫자 조각들로 만들 수 있는 모든 가능한 조합을 생성.
2. 각 조합이 소수인지 판별.
3. 중복된 숫자를 제거하여 유일한 소수의 개수를 계산.

제약 조건:

• 입력 문자열의 길이는 최대 7이므로 완전 탐색이 가능.
• 숫자 조합의 순서와 길이를 고려해야 함.

문제 해결 접근법

1. 모든 조합 생성 (완전 탐색)

숫자 조각으로 만들 수 있는 모든 조합을 탐색합니다. 재귀 호출을 사용해 숫자를 하나씩 추가하고, 추가한 숫자는 다시 탐색하지 않도록 방문 여부(visited)를 관리합니다.

2. 소수 판별

숫자 조합이 생성되면, 해당 숫자가 소수인지 판별합니다:

• 소수는 1과 자기 자신으로만 나누어 떨어지는 수입니다.
• 효율성을 위해 2부터 sqrt(number) 까지 나누어떨어지는지 확인합니다.

3. 중복 제거

set 자료구조를 사용해 중복된 숫자 조합을 자동으로 제거합니다.

4. 백트래킹 (Backtracking)

숫자 조합 탐색이 끝나면 이전 상태로 되돌아가 다른 경로를 탐색합니다:

• 탐색한 숫자는 다시 사용 가능하도록 방문 여부(visited)를 초기화.
• 이전 조합을 복원해 다른 경로를 탐색.

코드 설명

#include <string>
#include <vector>
#include <set>
#include <math.h>

using namespace std;

// 방문 여부와 생성된 소수를 저장하는 자료구조
vector<int> visited;
set<int> unit;

// 소수 판별 함수
int check(int number) {
    if (number == 0 || number == 1) return 0; // 0과 1은 소수가 아님
    for (int i = 2; i <= sqrt(number); i++) {
        if (number % i == 0) return 0; // 나누어떨어지면 소수가 아님
    }
    return 1; // 소수
}

// 숫자 조합 탐색 함수
void find(int nummer, vector<int>& nums) {
    for (int i = 0; i < nums.size(); i++) {
        if (visited[i]) continue; // 이미 사용한 숫자는 건너뜀
        string str = "";
        str += to_string(nummer);
        str += to_string(nums[i]);
        int let = stoi(str); // 새로운 숫자 조합 생성
        visited[i]++;
        if (check(let)) unit.insert(let); // 소수면 저장
        find(let, nums); // 재귀 호출로 다음 조합 탐색
        visited[i]--; // 원복 (Backtracking)
    }
}

// 메인 함수: 입력 문자열 처리 및 탐색 시작
int solution(string numbers) {
    int answer = 0;
    vector<int> nums;
    for (auto c : numbers) {
        nums.push_back(c - '0'); // 각 숫자를 벡터에 저장
    }

    // 모든 숫자 조각에서 탐색 시작
    for (int i = 0; i < nums.size(); i++) {
        visited = vector<int>(nums.size());
        visited[i]++;
        if (check(nums[i])) unit.insert(nums[i]); // 단일 숫자가 소수인지 확인
        find(nums[i], nums); // 조합 탐색 시작
    }

    answer = unit.size(); // 중복 제거된 소수 개수
    return answer;
}

배운 점

1, 완전 탐색과 백트래킹:

• 모든 가능한 숫자 조합을 탐색하기 위해 재귀 호출을 사용했습니다.
• 탐색 후 상태를 원래대로 복원(Backtracking)하여 다른 경로를 탐색할 수 있도록 했습니다.

2, 효율적인 소수 판별:

• 2부터  sqrt(number) 까지만 나누어 소수를 판별하여 성능을 최적화했습니다.
• 소수 판별 조건을 명확히 정의해 number≤1 은 항상 소수가 아님을 처리했습니다.

3, 중복 제거의 중요성:

• 숫자 조합 생성 시 set을 활용해 중복된 숫자를 자동으로 제거함으로써 결과의 정확성을 보장했습니다.

4, 문자열 처리와 숫자 변환:

• 숫자 조각을 문자열로 결합 후 다시 정수로 변환하여 숫자 조합을 생성하는 방법을 익혔습니다.

결론

이 문제를 통해 완전 탐색, 백트래킹, 소수 판별 및 중복 제거의 중요성을 다시 한번 깨달았습니다. 탐색과 원복의 정확성을 유지하면서 최적의 결과를 도출하기 위한 효율적인 구현 방식을 배울 수 있었습니다.

앞으로도 탐색 문제에서 이런 접근 방식을 활용할 수 있을 것입니다! 😊