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

풀이

문제는 간단한데 생각보다 어려운 문제였다.

어려웠던 부분은 "어떻게 하면 쪼개서 나열할 수 있을까?" 였다.

이 과정에서 결국 답을 봤지만, 생각보다 간단했다.

쪼개고, 순열 돌리기

주어진 numbers의 문자열을 하나씩 문자 형태로 쪼개서 배열에 넣어준 다음에,

그 배열을 정렬하고 순열을 돌리면 된다.

 

예시를 보자.

numbers = "17"; 이라는 문자열이 들어오게 되면
paper[0] = '1';
paper[1] = '7';

이렇게 쪼개서 넣어준 다음에, 해당 배열을 정렬한다.

정렬하는 이유는 순열을 돌리기 위한 전제 조건이기 때문에 꼭 해주자. 정렬을 하지 않으면 처음부터 끝까지 모든 순열의 정보를 얻을 수 없기 때문이다.

 

순열을 돌리면 아래와 같이 2가지의 경로가 나오게 된다.

차례대로 하나씩 정수형으로 변환하여 넣어주면 아래와 같게 만들어진다.

첫 번째 순열 결과 : '1', '7' -> "1", "17" -> 1, 17
두 번째 순열 결과 : '7', '1' -> "7", "71" -> 7, 71

set<int> : 1, 7, 17, 71

여기서 set을 사용한 이유는 중복될 수 있기 때문에 사전에 중복된 숫자는 지워주기 위해서 사용했다.

종이로 만들 수 있는 모든 숫자를 만든 뒤에 해당 숫자가 소수인지 아닌지 파악하는 간단한 소수 함수를 만들어서 판별하면 답을 구할 수 있게 된다.

bool isPrime(int n) {
    if (n == 0 || n == 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

전체 소스 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;

bool isPrime(int n) {
    if (n == 0 || n == 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int solution(string numbers) {
    int answer = 0;
    vector<char> paper;
    set<int> s;
    for (char c : numbers) paper.push_back(c);

    sort(paper.begin(), paper.end());
    do {
        string temp;
        for (int i = 0; i < paper.size(); i++) {
            temp += paper[i];
            s.insert(stoi(temp));
        }
    } while (next_permutation(paper.begin(), paper.end()));

    for (int n : s) {
        if (isPrime(n)) answer++;
    }

    return answer;
}