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

▶문제설명

코딩테스트 연습 > 완전탐색 > 소수 찾기

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

▶ 설계

---

number의 길이를 n이라고 하자.

n개의 숫자들 중에 1 ~ k 개를 뽑아서 순열을 생성한 뒤 정수로 변환하고 해당 정수가 중복되지 않도록하여 소수인지 아닌지 판별해서 개수를 반환하는 함수를 구현해야 한다.

조합의 경우에는 순서를 고려하지 않고 k개를 뽑아내므로 조합만으로는 풀 수 없다. 

(간단히 예를 들면 1, 3, 2 를 뽑아낼 뿐이지 132, 123, 213, 231, 312, 321와 같이 순열을 뽑아내는 방법이 아니기 때문이다.)

n개의 숫자들 중 k개를 뽑아서 순열을 만들기 위해서 재귀함수를 구현하면 될 것으로 보인다.

void permutation(string& numbers, int idxNow, int k, int cntSelectedNum, vector<int>& ansPrimeNumbers){
    if(cntSelectedNum == k){
        return;
    }
    
    for(int i=idxNow ; i<numbers.length() ;i++){
        swap(numbers[i], numbers[idxNow]);
        permutation(numbers, idxNow+1, k, cntSelectedNum+1, ansPrimeNumbers);
        swap(numbers[i], numbers[idxNow]);
    }
}

종료 조건은 cntSelctedNum(선택된 숫자들의 개수)이 k와 같을 때이다.

이 때가 바로 k개의 숫자로 순열이 만들어진 시점이므로 문자열을 정수로 바꿔 소수인지 판별하면 된다.

하지만 순열이 중복될 수 있으므로 

set<int> checkSet;

set 자료구조를 사용해서 중복을 제거해주도록 하자.

▶ 구현

---

직접 정의한 순열을 생성하는 permutation()은 세 번째 인자로 1부터 numbers.length()까지의 값을 주어 호출했다.

그러면 1개를 뽑아 만든 순열, 2개를 뽑아 만든 순열, ... , numbers.length()개를 뽑아 만든 순열을 생성한다는 의미다.

cntSelectedNum == k가 참이 되어 순열이 생성된 시점에

문자열을 정수로 바꾸고 checkSet에 이미 해당 정수가 있는지 확인해서 중복을 체크했다.

set 자료구조는 key값이 중복되지 않도록 구현되어 있기에 가능했다.

int getInt(string strNum){
    int ret = 0;
    for(int i=0; strNum[i] ; i++){
        ret = (ret*10) + strNum[i]-'0';
    }
    return ret;
}

위와 같은 소스를 통해 문자열을 정수로 변환할 수 있었다.

제일 앞쪽에 있는 숫자부터 순차적으로 현재 정수에 10을 곱한 값에다 더해주었다.

이 방법으로 "0234"가 정수 234로 바뀌는 과정을 보면

0(초기값) -> 0 -> 2 -> 23 -> 234 

이런식으로 값이 만들어진다는 것을 알 수 있다.

또한, 만들어진 정수가 소수인지 판별해서 카운트 해줘야 한다.

소수를 판별하는 부분은 [2, sqrt(num)] 범위를 훑으면서 자기 자신을 제외한 수로 나누어 떨어지는지 확인해서 그런 경우가 하나라도 있다면 false를 반환하도록 구현했다.

▶Solution

---

[소스코드 보기]