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

문제 풀이

 

 

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int solution(string numbers) {
    int answer = 0;

	// string 타입의 numbers를 int로 받아올 벡터 생성
	vector<int> num;

	// 현재 numbers는 string 형태이기 때문에 int형으로 받아오게 되면 숫자가 달라진다. ex) string 타입의 "0"은 int타입으로 48.
	// 때문에 '0'을 빼서 int형태에 맞게 숫자를 맞춰준다.
	for (auto it : numbers) num.push_back(it - '0');

	// next_permutation을 사용하기 위해 오름차순으로 정렬해준다. 왜냐하면 
	// next_permutation은 다음에 나온 순열이 순서상 이전 순열보다 작다면 false를 반환(루프 탈출)하기 때문이다.
	// 즉, 큰 숫자가 앞에 있으면 다 돌기도 전에 끝이 날 수 있다.
	sort(num.begin(), num.end());

	// 순열(숫자의 조합들)을 저장할 배열 생성
	vector<int> per;

	// do_while문으로 실행하는 이유는 순열을 시작하기 전 첫 번째 경우의 수도 포함하기 위해서이다. 
	// 그냥 while로 돌리면 첫 번째 경우의 수를 포함하지 않는다.
	// next_permutation은 순열을 구하는 알고리즘이다.
	do {

		// 숫자를 하나만 사용하는 것부터 전부 다 사용하는 것까지 돌아가는 for문.
		// 경우의 수를 모두 조합해보기 위해 사용한다.
		for (int i = 0; i <= num.size(); i++) { 
			
			// 각 숫자를 저장할 변수. "123"이라면 1, 2, 3, 12, 13 ...등을 저장하게 될 것이다.
			int tmp = 0;
			
			// j < i가 포인트이다. 0부터 시작해서 i 전까지 가기 때문에 숫자가 1개일 때, 숫자가 2개 이상일 때를 모두 확인할 수 있다.
			for (int j = 0; j < i; j++) {
				
				// tmp * 10을 하는 이유는 첫 번째 숫자가 들어왔을 때 이후에 들어올 num[j]와 겹치지 않게 하기 위함이다.
				// 문자열 1에 2를 더하면 12가 되는 원리와 같다. 동일하게 12에 3을 더하면 123이 되는 것.
				tmp = (tmp * 10) + num[j];
				
				// 해당 숫자를 per에 저장한다.
				per.push_back(tmp);
			}
		}
	
	// 이 do_while문은 num을 기준으로 돌아간다. 즉 [1, 2, 3]의 배열이 있다면 123, 132, 213 ... 순으로 순열을 만들어 계속 돌아가는 것이다.
	} while (next_permutation(num.begin(), num.end()));


	// per에서 중복된 값을 제거하기 위해 정렬 실행
	sort(per.begin(), per.end());

	// 위에서 정렬을 실행하는 이유는 unique가 "연속으로 중복된" 값을 처리하기 때문이다.
	// (1, 1, 2, 3, 2, 3)을 unique 하면 (1, 2, 3, 2, 3, 3)으로 처리된다. 때문에 반드시 정렬을 해야 함.
	// unique와 erase를 같이 썼는데, unique의 return 값은 유일한 원소들이 끝나고 첫 번째 쓰레기 원소가 나오는 곳의 위치이다.
	// erase는 이 쓰레기 원소의 위치부터 지워주는 역할을 한다. erase와 unique는 같이 쓰는 것이라고 생각하면 된다.
	per.erase(unique(per.begin(), per.end()), per.end());
	
	// per에 있는 숫자가 소수가 맞는지 판별
	for (int i = 0; i < per.size(); i++) {
		
		// 소수인지 판별을 위한 bool 변수 생성
		// true이면 소수이고 false이면 소수가 아니다.
		bool flag = true;

		// 2보다 작은 수는 소수라고 하지 않는다. 때문에 false
		if (per[i] < 2) flag = false;

		// per[i]의 제곱근이 j와 같거나 클 경우에 검사. 어떤 수(X)이건 간에 최대 약수는 X / 2이다. 즉 중간까지만 검사해보면 된다.
		for (int j = 2; j<= sqrt(per[i]); j++) {

			// j로 나누어 떨어진다는 것은 j라는 약수가 존재한다는 뜻이 된다. 때문에 소수가 아님
			if (per[i] % j == 0) flag = false;
		}

		// 위의 조건문을 모두 통과해 왔다면 소수로 판별이 된다. 때문에 answer++
		if (flag) answer++;
	}

    return answer;
}

 

 

 

문제 링크

 

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

코딩테스트 연습 - 소수 찾기