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

이 글에서는 프로그래머스 - 소수 찾기 문제에 대해 다뤄보겠습니다. 문제 풀이는 C++로 이루어져 있고 함께 들어가 있는 개념들도 간단히 정리 해보는 형식으로 작성되었으므로 오타등의 오류가 있을 수 있습니다. 오류 발견시 댓글로 꼭 말씀해주세요! 시작해볼까요?

 

문제의 핵심이 무엇인가.... 라고 물어 본다면 '소수 찾기'는 아닌 것 같습니다. 소수 찾기라면 프로그래밍을 배우고 얼마 지나지 않아 바로 과제로 나오는 함수(예를 들면 isPrime을 짠다던지 그렇다던지 그렇쟌습네까?) 중 하나지 않습니까? 소수를 찾지 못해서 문제를 못 푸는 것은 아닌 것 같습니다. 문제의 분류가 greedy algorithm에 있다는 것에 의심을 가득 품고 문제를 열어보면 핵심은 종이 쪼가리의 combination & permutation이 핵심이지 않을까.... 라는 생각이 듭니다.

 

이 문제는 유독 말씀드리고 싶습니다. 제 답이 가장 효율적인 것이 아니며, 더 좋은 풀이들이 많다는 것 (아 물론 제 답이 젤 효율적일 수도 있지 키키 근데 이번건 아니에요 확실히~)을요.

 

일단 하나 명확히 하고 갈 것은 정말로 isPrime을 짤 수 있는가 입니다. isPrime 함수는 아래와 같이 작성하고 사용했습니다.

// returns true if prime_number
// returns false if it isn't prime_number
bool isPrime(int num){
    if(num == 1 || num == 0)
        return false;
        
    for(int i = 2; i < num; i++){
        if (num % i == 0){
            return false;
        }
    }
    return true;
}

---

풀이 1

종이 쪼가리를 모두 사용하라는 조건이 없으므로 모든 1장, 2장, .... n장 까지 사용할 수 있다는 뜻입니다. 어떻게 하면 좋을까 고민하다가 아래 [그림1]과 같이 구현을 해 보았습니다. 우선 모든 종이를 사용해서 나올 수 있는 permutation을 구합니다. 아래 예시와 같이 [3, 3, 1] 이렇게 3개의 숫자가 주어졌다고 합시다. 이들로 만들 수 있는 조합의 종류는 {133, 313, 331} 이겠죠?

이 때 하나의 조합을 substring으로 잘라내는 것입니다. 각각의 조합에 대해 길이가 1인, 2인.... n - 1인 substring으로 잘라내고 {133, 313, 331} 을 합치면 주어진 종이로 만들 수 있는 숫자들이 나옵니다.

물론 중복 되어있으므로 중복 제거도 하고, 소수인지 아닌지 판단을 해야 최종 답이 나오겠지만요. 

[그림 1] 핵심은 substring과 next_permutation

#24 ~ 27 : "311"과 같이 주어진 string을 하나씩 분리하여 vector에 삽입합니다

#29 ~ 41 : next_permutation을 통해 주어진 숫자를 모두 활용한 조합된 숫자들을 permutationNum에 삽입하게 됩니다. 이 뿐 아니라 (#36 ~ 40) 각 조합된 경우의 수를 길이 대로 잘라 permutationNum에 삽입하게 됩니다.

#43 ~ 46 : 위의 코드에서 substring을 사용해서 push_back을 진행했으므로 중복된 숫자들이 많으므로 중복을 삭제합니다.

#48 ~ 51 : 실질적인 답을 구하는 과정으로 각 숫자가 소수인지 검사 후 소수일 경우 답을 increment 합니다.

 

채점 결과 : 정확성 테스트(100.0) = 100.0

---

풀이 2

남들은 어떻게 푸나~ 궁금해서 검색을 해보면 신기하게 모두가 같은 방법으로 풉니다. 모두가 같은 알고리즘을 아는 것인지, 아니면 자신의 것을 버리고 다수가 택한 알고리즘으로 자신의 풀이를 바꾸는 것이지는 잘 모르겠지만 이번 문제는 다수가 에라토스테네스의 체를 활용해서 풀었다는 점입니다.

도대체 뭔가 싶어서 알아보니 오... 신기하게 다가왔습니다. 비슷한 상황이 오게 되면 굳이 소수를 구하는 상황이 아니더라도 사용해볼 수 있지 않을까 라는 생각이 들었습니다. 에라토스테네스의 체를 문제에 적용해 보면 다음과 같습니다.

 

[그림 2]

주어진 숫자로 만들 수 있는 가장 큰 숫자를 만듭니다. 우리의 예시에서는 331 이겠죠? 그러면 2부터 331까지의 소수를 모두 구하는데 이 때 그 소수가 3 / 3 / 1 을 포함하는 지 확인하는 것입니다. 위 gif를 보면 Prime numbers 리스트가 만들어지죠? 저 리스트(구현하면 vector에 들어가겠지만)의 숫자들에 3 / 3 / 1 이 포함되어 있는지 확인하면 됩니다.