[프로그래머스 Lv.2 / C++] Day73. 소수 찾기

2024. 08. 15 - 코딩테스트 스터디 Day73

 
 

01. 문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해 주세요.

 
 

02. 제한사항

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

 
 

03. 입출력 예

numbers	return
"17"	3
"011"	2

 

📌 입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.
 
예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

 
 

4. 풀이 및 답

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

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> uniquePrimes;    // 중복 값 자동 제거
    
    sort(numbers.begin(), numbers.end());
    
    do {
        for (int i = 1; i <= numbers.size(); i++) {
            string tmp = numbers.substr(0, i);  // 부분 문자열 추출
            int num = stoi(tmp);
            if (isPrime(num)) {
                uniquePrimes.insert(num);
            }
        }
    } while (next_permutation(numbers.begin(), numbers.end())); // 모든 조합 숫자 생성
    
    answer = uniquePrimes.size();
    
    return answer;
}

우선 unordered_set 자료형은 집합(Set)처럼 동작하여, 중복된 값을 자동으로 없애준다. 따로 처리할 필요 없이 중복된 값을 제거해 주기 때문에 편리하다. 이 unordered_set 타입의 uniquePrimes를 사용하여 중복되지 않는 소수값들을 모아둘 수 있다.
 
numbers 문자열을 오름차순 정렬한다 (참고로 뒤에 설명할 next_permutation 함수는 오름차순 되어있는 배열만을 처리할 수 있다.
오름차순 정렬한 numbers 문자열을 substr 함수를 통해 부분 문자열을 출력하고 이 문자열을 정수로 변환한다.

numbers가 "123"이었다면
"1", "12", "123"

 
이렇게 정수로 변환된 값이 소수라면 uniquePrime 집합에 추가한다.
 
next_permutation 함수는 문자열의 모든 순서를 조합하여 나올 수 있는 모든 숫자를 생성해 주는 함수이다. 

예를 들면 "123"을 "132", "213", "231", "312", "321"로 재배열해 나타내는 것이다.

 
최종적으로 uniquePrimes 집합에 있는 수의 개수를 반환해 주면 된다.
 

정답!

---

끝