[프로그래머스] 소수 찾기

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

 

풀이

이 문제가 그렇게 쉽진 않습니다. C++에서 지원되는 함수가 있어서 쉽게 풀리는 것이지요. 검색해보면 풀이 코드가 거의 다 비슷합니다. 다 비슷한데 설명은 거기거 거기입니다. 이 문제의 핵심은 순열을 구하는 함수를 반복적으로 호출해, 조합할 수 있는 모든 경우의 숫자를 구하는 것입니다. 종이 조각을 이용해 만들 수 있는 모든 조합을 구하는 방법은 크게 두 가지로 DFS를 이용하거나, 순열 구하는 함수 next_permutation()/prev_permutation()을 이용합니다. DFS를 이용하는 것은 나중에 다뤄보겠습니다.

 

next_permutation() 함수는 오름차순을 해놓고 시작해야 합니다. 가령 "1324"라는 문자열이 주어지면 "1234"로 정렬한 뒤 함수를 돌려야 "4321"로 끝납니다. prev_permutation() 함수는 내림차순을 해놓고("1324"->"4321") 실행해야 합니다. 저는 prev_permutation() 함수를 사용해봤습니다. 이 함수들은 마지막 순열을 만들고 나서 처음 상태로 reset이 되고 false를 반환합니다. 기본적인 아이디어는 "4321"로 정렬하고 나서 "4", "43", "432", "4321"를 숫자로 변환해 소수인 것만 set 컨테이너에 넣는 것입니다. set은 연관 컨테이너로서, 다루는 오브젝브 젝트가 값이면서 키이기 때문에, 고유값만 삽입됩니다. 보통 레드블렉 트리로 구현된다고 합니다. 다음 순열이 "4312"라면 "4", "43", "431", "4312"를 숫자로 변환해 소수인지를 판별하면 됩니다.

 

set 컨테이너로 중복 제거한 경우

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

using namespace std;

bool isPrime(int num)
{
    if(num == 1 || num == 0) return false;
    for(int i = 2; i*i <= num; ++i)    
        if (num % i == 0) return false;
    return true;
}

int solution(string numbers) {
    sort(numbers.begin(), numbers.end(), [](char a, char b){ return a > b;});
    set<int> answer;
    do
    {        
        for (int i = 1; i <= numbers.size(); ++i)
        {            
            int num = stoi(numbers.substr(0, i));
            if (isPrime(num))
                answer.insert(num);
        }
    } while(prev_permutation(numbers.begin(), numbers.end()));
    
    return answer.size();
}

 

vector 컨테이너로 중복 제거한 경우

set 컨테이너를 안 쓰고 vector로도 중복 제거를 할 수는 있습니다. unique라는 함수를 이용하면 되는데요. 동작 방식이 중복된 값을 만나면 이동시키면서 지우기 때문에, 오름차순이든 내림차순이든 정렬을 한 번 하고 나서 unique 함수를 써야 합니다. 반환값은 중복을 제거한 범위의 end iterator이기 때문에 erase 함수를 호출해서 불필요한 데이터를 삭제해줘야 해요. 그런 만큼 속도가 느립니다. 코드도 복잡해지고 성능이 떨어진 걸 테스트로 확인할 수 있습니다.

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

using namespace std;

bool isPrime(int num)
{
    if(num == 1 || num == 0) return false;
    for(int i = 2; i*i <= num; ++i)    
        if (num % i == 0) return false;
    return true;
}

int solution(string numbers) {
    sort(numbers.begin(), numbers.end(), [](char a, char b){ return a < b;});
    //set<int> answer;
    vector<int> answer;
    do
    {        
        for (int i = 1; i <= numbers.size(); ++i)
        {            
            int num = stoi(numbers.substr(0, i));
            if (isPrime(num))
                answer.push_back(num);
                //answer.insert(num);
                
        }
    } while(next_permutation(numbers.begin(), numbers.end()));
    sort(answer.begin(), answer.end());
    answer.erase(unique(answer.begin(), answer.end()), answer.end());    
    return answer.size();
}

vector 사용

set 사용