프로그래머스 소수 찾기

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

프로그래머스

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers return

"17"	3
"011"	2

 

---

 

음…푸는데 한시간 정도 걸린 것 같다.

문제만 봤을 때는 쉬워 보였는데 막상 해보니깐 순열을 구하면서 중복되는 값을 고려해야 하고, 전부 자릿수도 다르니 답답했다.

1시간 중에 어떻게 풀어야 할지 30분은 고민하면서 사용한 것 같다.

나는 코드를 조금 쉽고 간단하게 풀고 싶었다.

그렇게 해서 나온 아이디어는 다음과 같다.

 

알고리즘

1. 중복되는 순열을 제거해 주기 위해 unordered_set을 선언하였다.
2. 숫자들을 정렬하여 순열을 통해 중복된 조합을 피해주었다. (예를 들어, "011"과 "110"은 같은 조합이다. 이를 위해 정렬을 사용하여 숫자의 순서를 일정하게 유지한다)
3. 현재 순열의 부분 문자열 생성해준다.
4. 부분 문자열을 숫자로 변환해준다.
5. 소수 인지 판단해주고, 소수인 경우 집합에 추가해준다.
6. 1~5를 반복해준다. 순열을 전부 만들어줄 때까지
7. unordered_set의 사이즈를 반환해준다.

 

코드

#include <string>
#include <vector>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <unordered_set>

using namespace std;

bool isPrime(int num) {
    if (num <= 1) return false; 

    for (int i = 2; i <= sqrt(num); ++i) {
        if (num % i == 0) {
            return false; 
        }
    }
    return true;
}

int solution(string numbers) {
    int answer = 0;
    unordered_set<int> num;

    sort(numbers.begin(), numbers.end()); // 숫자들을 정렬하여 순열을 통해 중복된 조합을 피함

    do {
        for (int i = 1; i <= numbers.size(); ++i) {
            string temp = numbers.substr(0, i); // 현재 순열의 부분 문자열 생성
            int num_temp = stoi(temp); // 부분 문자열을 숫자로 변환
            if (isPrime(num_temp)) {
                num.insert(num_temp); // 소수인 경우 집합에 추가
            }
        }
    } while (next_permutation(numbers.begin(), numbers.end())); // 다음 순열 생성

    return num.size(); // 중복을 제거한 소수의 개수 반환
}

위의 코드에서 핵심 부분은

do {
        for (int i = 1; i <= numbers.size(); ++i) {
            string temp = numbers.substr(0, i); // 현재 순열의 부분 문자열 생성
            int num_temp = stoi(temp); // 부분 문자열을 숫자로 변환
            if (isPrime(num_temp)) {
                num.insert(num_temp); // 소수인 경우 집합에 추가
            }
        }
    } while (next_permutation(numbers.begin(), numbers.end())); // 다음 순열 생성

이 부분이다.

 

위 코드는 순열을 생성해주는 코드이다.

수학적으로 순열(permutation)이란 서로 다른 n개의 원소에서 r개를 뽑아 한 줄로 세우는 경우의 수를 말합니다. 원소를 한 줄로 세우기 때문에 원소의 조합이 같더라도 순서가 다르면 다른 방법으로 봅니다.    예를 들어 집합 {1, 2, 3}의 원소들의 모든 순열을 구한다면 {1, 2, 3} {1, 3, 2} {2, 1, 3} {2, 3, 1} {3, 1, 2} {3, 2, 1} 로 총 6가지가 나오게 됩니다.

출처: https://mjmjmj98.tistory.com/38

 

: next_permutation

C++의 algorithm 헤더에는 n개의 원소의 순열을 구할 수 있는 next_permutation이라는 함수가 있습니다. 기본적 문법은 다음과 같습니다.

// default
bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last);
 
// custom
bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last, Compare comp);

next_permutation은 순열을 구할 컨테이너(쉽게 말해 배열)의 시작과 끝 iterator를 인자로 받습니다. 만약 해당 컨테이너에 다음 순열이 존재하면 그 컨테이너의 원소를 해당 순열 순서로 바꾸고 true를 반환하고, 다음 순열이 없다면 false를 반환합니다. 위 코드의 custom에서 볼 수 있듯이 비교 함수 comp를 인자로 넘기는 것도 가능합니다.

 

예시

int a[3] = { 1, 2, 3 };

	do {
		for (int i = 0; i < 3; ++i)
			cout << a[i];
		cout << '\\n';
	} while (next_permutation(a, a + 3));

	/*
	123
	132
	213
	231
	312
	321
	*/

여기에서 영감을 받아 unordered_set과 함께 이용하여 코드를 구현하였다.