[프로그래머스] 소수 찾기 (완전탐색 Lv. 2) - C++

0. 자세한 설명은 영상으로

 

1. 문제 설명 (출처 : 프로그래머스, 원 출처)

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한조건

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers	return
"17"	3
"011"	2

입출력 예 설명

• 예제 #1
  • [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.
• 예제 #2
  • [0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.
  • 11과 011은 같은 숫자로 취급합니다.

 

2. 문제 접근 방식 (문제 단순화 하기)

• 늘 그렇듯, 문제를 간단하게 만들어보는 것이 1단계이다.
• 완전 탐색 유형은 가장 단순하고 그래서 참 쉽다.
• 하나도 빠짐없이 모든 경우의 수를 확인하고 있는지만 확인하면 된다.
• 이 문제의 경우에는 숫자 카드 7장으로 만들 수 있는 모든 숫자를 만들었는지를 첫 번째로 확인해야 하고
• 만든 모든 숫자가 소수인지 확인하면 된다.

 

 

 

 

 

 

3-1. Set / 재귀함수를 활용한 Solution

#include <iostream>
#include <string>
#include <set>
#include <cmath>

using namespace std;

set<int> numberSet;

bool isPrime(int number)
{
    // 1. 0과 1은 소수가 아니다 (소수의 정의)
    if (number == 0 || number == 1)
        return false;

    // 2. 에라토스테네스의 체
    int lim = sqrt(number);
    for (int i = 2; i <= lim; i++)
        if (number % i == 0)
            return false;

    return true;
}

void makeCombination(string comb, string others)
{
    // 1. 현 조합을 numberSet에 추가한다.
    if (comb != "")
        numberSet.insert(stoi(comb));

    // 2. 현 조합 + others[i]를 조합하여 새로운 조합을 만든다.
    for (int i = 0; i < others.size(); i++)
        makeCombination(comb + others[i], others.substr(0, i) + others.substr(i + 1));
}

int solution(string numbers)
{
    // 1. 모든 숫자 조합을 만든다
    makeCombination("", numbers);

    // 2. 소수의 개수를 센다
    int answer = 0;
    for (int number : numberSet)
        if (isPrime(number))
            answer++;

    // 3. 소수의 개수를 반환한다.
    return answer;
}

int main(void)
{
    cout << solution("117");
}

1) 전체 solution 풀이

• 재귀 함수로 모든 카드의 조합을 만들어본다.
• 만들어진 숫자는 numbersSet에 만들어지니, 각 숫자가 소수인지 확인한다.

 

2) 재귀함수를 통해 모든 숫자 조합을 만든다.

• 재귀함수를 사용해 모든 숫자 조합을 만든다.
• 재귀의 기본적인 동작은 현 combination + others의 i번째 character를 조합한다.

 

3) 현 combination이 prime인지 확인한다.

• 에라토스테네스의 체란 2-MaxNum까지 전부 배수인지 확인할 필요가 없다는 것을 증명한 수학적인 이론이다.
• 예를 들어 97이라는 숫자가 소수인지 아닌지를 확인하고 싶다면, 97이 2~96 전부의 배수인지 확인할 필요가 없고,
• 2~sqrt(96)의 배수인지만 확인하면 된다는 이론이다. 
• 그렇기 때문에 우리도 isPrime 함수에서 전부를 보지 않고, sqrt한 값까지만 확인하고 비교한다.
• 이렇게 만들어진 prime_set이 정답을 전부 가지고 있으니, len(prime_set)이 소수의 개수가 된다.

 

4. 참 쉽죠?

• 완전 탐색은 참 쉽다. 빠짐없이 모든 경우의 수를 다 따져보기만 하면 되는데, 컴퓨터는 이런 것을 하는 데 최적화되어있는 존재다.
• 이번 문제의 필자의 해결책이 최선은 아닐 것 같다. 사실 이렇게 정직하게 모든 경우를 확인해서 통과할 수 있을지 의심이 되기도 했지만, 1차 답안이라 생각하고 제출한 게 통과가 되어버렸다.
• 물론 실제 코딩 테스트에서는 최적화를 위해 고민하겠고, 훨씬 더 빠르고 간결한 답안이 많겠지만 완전 탐색은 완전 탐색답게 풀어봤다.
• 이렇게 단순한 생각/로직으로 작성한 코드는 가독성이 좋다는 정신승리로 이번 포스트는 마무리한다.