프로그래머스 문제 풀이 소수 찾기

문제 URL 소수 찾기

Contents

1. 문제 지문 파악하기
2. 구르미의 알고리즘 풀이

문제 지문 파악하기

이번에도 문제의 입력을 통해서, 문제를 파악해보도록 하겠습니다. 다음은, 첫 번째 입력입니다.

 

입력:
numbers = "17"

 

numbers를 통해서 만들 수 있는 문자열의 모든 경우의 수는 다음과 같습니다.

 

permutations = [ "1", "7", "17", "71" ]

 

각각 numbers에서 1개를 선택했을 때, 만들 수 있는 경우의 수와 2개를 선택했을 때 만들 수 있는 경우의 수를 합쳐진 것을 알 수 있습니다.

 

numbers에서 1개를 선택했을 때 만들 수 있는 경우의 수:
["1", "7"]

numbers에서 2개를 선택했을 때 만들 수 있는 경우의 수:
["17", "71"]

 

이 경우의 수에서 소수인 숫자의 개수를 구하면 됩니다. permutations에서 소수는 7, 17로 2개입니다. 따라서 정답은 2개이지요. 즉, 이 문제에서 중요한 것은, 소수를 판별하는 알고리즘과, 개수가 주어졌을 때, numbers에서 해당 개수를 골라 순열을 만드는 알고리즘이 중요합니다.

 

소수 판별 식은, 흔히들 이용하는 "에라토네스의 체"를 이용한 알고리즘을 사용할 것입니다. 이를 파이썬 코드로 만들면, 다음과 같습니다.

 

def is_prime(number): if number < 2: return False if number == 2 or number == 3: return True for i in range(2, int(number ** 0.5) + 1): if number % i == 0: return False return True

def is_prime(number):
    if number < 2:
        return False
    
    if number == 2 or number == 3:
        return True

    for i in range(2,  int(number ** 0.5) + 1):
        if number % i == 0:
            return False

    return True

 

이제 numbers에서 cnt만큼 골라서 만들 수 있는 모든 경우의 수, 즉 순열을 만들어봅시다. (숫자의 순서에 따라 값이 다르기 때문에 조합은 쓸 수 없습니다.) 이 때, 방법은 크게 2가지가 있습니다. 먼저, DFS를 이용하는 방법, 두 번째로는 재귀를 이용하는 방법입니다. 저는 "재귀"를 통해서 순열을 만들어보겠습니다.

 

def permutations(result, numbers, string, idx, cnt):
    # 1. 재귀 탈출 부 idx (string의 길이) == cnt
    # 탈출할 때, 여지껏 만든 string을 result에 넣어준다.
    if idx == cnt:
        result.append(int(string))
    
    for i, num in enumerate(numbers):
        # 1. 선택한 문자를 제외한 문자열을 만든다.
        n = numbers[:i] + numbers[i+1:]
        # 2. 선택한 문자를 string에 더해준다.
        s = string + num
        # 3. 재귀 호출.
        permutations(result, n, s, idx + 1, cnt)

 

먼저 재귀 탈출부부터 살펴봅시다. idx는 string에 마지막 인덱스/길이를 뜻합니다. 즉 idx == cnt라는 것은 고르고 싶은 문자들의 개수를 채웠다는 뜻입니다.

 

그리고 반복문에서, 문제의 입력을 줄여주는 코드가 바로 n을 구하는 코드입니다. 해당 인덱스의 문자를 빼고, 새로운 문자열을 만들어줍니다. 그리고 string은 해당 문자를 선택하면, 더해주는 것이죠.

 

한 번, 특정 예제를 통해서 어떻게 동작할까 손으로 풀어보세요. 분명 "재귀 호출을 이용한 완전 탐색"에 대해서 더 깊은 이해를 할 수 있을겁니다.

구르미의 알고리즘 풀이

"문제 지문 파악하기"를 토대로 세운 알고리즘을 순서대로 나열하면 다음과 같습니다. (소수판별, 순열을 생성하는 알고리즘은 큰 줄기로써 설명하지 않습니다.)

 

1. numbers를 기준으로 1 ~ n개를 선택해서 만들 수 있는 경우의 수들을 만듭니다. 이 때, 중복은 저장하지 않습니다.
2. 만들어진 수들 중 소수인 숫자의 개수를 구합니다.

이를 조금 더 프로그래밍적으로 표현하면 다음과 같습니다.

 

1. 집합 s를 만듭니다.
2. i에 대해서, 1 ~ n까지 다음을 반복합니다.
   1. numbers에서 i개를 선택하여, 만들 수 있는 숫자의 경우의 수들을 result에 저장합니다.
   2. 집합 s에 result의 원소들을 저장합니다. (이 때, 중복 저장은 허용되지 않습니다.)
3. s의 원소 중 소수의 개수를 구합니다.

다음을 코드로 나타내면 다음과 같습니다. 먼저 파이썬 코드입니다.

 

PYTHON 코드

def is_prime(number):
    """
    에라토네스의 체를 이용한 소수 판별 알고리즘입니다.
    """
    if number < 2:
        return False
    
    if number == 2 or number == 3:
        return True

    for i in range(2,  int(number ** 0.5) + 1):
        if number % i == 0:
            return False

    return True


def permutations(result, numbers, string, idx, cnt):
    """
    numbers에서 cnt개수 만큼 원소를 골라 만든 순열 리스트를 만들어줍니다.
    """
    if idx == cnt:
        result.append(int(string))
    
    for i, num in enumerate(numbers):
        permutations(result, numbers[:i] + numbers[i+1:], string + num, idx + 1, cnt)


def solution(numbers):
    # 1. 집합을 생성합니다.
    s = set()
    
    # 2. numbers에서 1개, 2개 .. 모두 골랐을 때, 만들 수 있는 수들의 순열을 구해서 집합에 더합니다.
    for i in range(1, len(numbers) + 1):
        result = []
        permutations(result, numbers, '', 0, i)
        s |= set(result)
    
    # 3. 집합에 저장된 원소 중, 소수 인 개수를 셉니다.
    answer = len( [x for x in s if is_prime(x)] )        
    return answer

 

이번엔 CPP 코드입니다. 알고리즘은 동일하고, 언어만 바뀐 것입니다.

 

CPP 코드

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

using namespace std;

bool is_prime(int number) {
    if (number < 2) {
        return false;
    }
    
    if (number == 2 || number == 3) {
        return true;
    }
    
    for(int i=2; i<=sqrt(number); i++) {
        if((number % i) == 0) {
            return false;
        }
    }

    return true;
}

void permutations(vector<int> & result, string numbers, string str, int idx, int cnt) {
    if (idx == cnt) {
        result.push_back(stoi(str));
        return;
    }
    
    for (int i=0; i<numbers.length(); i++) {
        permutations(result, numbers.substr(0, i) + numbers.substr(i+1), str + numbers[i], idx + 1, cnt);
    }
}

int solution(string numbers) {
    set<int> s;
    
    for (int i=1; i<=numbers.length(); i++) {
        vector<int> result;
        permutations(result, numbers, "", 0, i);
        s.insert(result.begin(), result.end());
    }
    
    int answer = 0;
    
    for (const auto & elem : s) {
        if (is_prime(elem)) {
            answer += 1;
        }
    }
    
    return answer;
}

 

참고적으로 파이썬의 경우, itertools.permutations 함수로 따로 함수를 작성하지 않아도 순열의 경우의 수를 만들 수 있습니다. 이것을 이용하면, 다음의 코드로 간단하게 문제를 풀 수 있습니다.

 

PYTHON 코드

# 소수 판별 함수는 이전과 동일합니다.
def is_prime(number):
    pass

# itertools.permutations를 이용해서 코드를 줄인 함수.
def solution(numbers):
    from itertools import permutations

    n = len(numbers)    
    s = set( int(''.join(result_set)) for i in range(1, n+1) for result_set in permutations(numbers, i) )
    answer = len([ x for x in s if is_prime(x) ])
    return answer

 

solution 함수만 봤을 때, import 구문을 제외하고 단 4줄이면 문제를 풀 수 있습니다!. 파이썬 짱짱..