[프로그래머스] 소수 찾기 - 완전탐색 (C++)

c++언어에 익숙해지기

파이썬 원툴 코테에서 c++ 코테로 전이하는 과정...

 

---

 

(삽질 과정 모두 포함)

(정답만 있는 포스트 아님)

 

한 자리 숫자가 적힌 종이조각이 흩어져 있다.

흩어진 종이조각을 붙여 소수를 몇 개 만들 수 있는지 알아내자

종이 조각에 적힌 문자열 numbers가 주어졌을 때

종이조각으로 만들 수 있는 소수가 몇 개인지 return하자

 

아이디어1: 일단 str 형태로 숫자가 줄줄 붙어서 나온다.

파이썬이었다면 list에 담아서 배열로 만들었을 것 같다

c++은 어떻게 할 수 있을까?

 

str.copy()를 사용해보자

 

#include <string>
#include <vector>
#include <iostream>
#include <cstring>

using namespace std;

int solution(string numbers) {
    int answer = 0;
    char chars[numbers.length()+1];
    numbers.copy(chars,numbers.length()+1);
    
    for(int i=0; i<numbers.length();i++){
        cout<<chars[i]<<endl;
    }
    return answer;
}

 

오 출력하니까 잘 나온다

 

근데 아직 char 원소여서 int 원소로 바꿔보자

 

그 사이에 str 문자열을 int로 바꾸는 방법을 생각해봤다

int numbers_ = stoi(numbers);
    cout<<numbers_<<endl;

근데 이렇게 했더니 011->11이 된다...

 

    int answer = 0;
    char chars[numbers.length()+1];
    numbers.copy(chars,numbers.length());
    int ints[numbers.length()+1];
    
    for(int i=0; i<numbers.length();i++){
        ints[i]=chars[i]-'0';
        cout<<ints[i]<<endl;
    }

 

정말 비효율적으로 생겼죠?

c++ 초보임을 감안해주셍요

 

아까 char배열로 바꾼 각 요소를

같은 길이의 int 배열에 int 요소로 바꿔서 넣어줬다

 

음... 근데 아무리 생각해도 이런 식으로 만들면 안될 것 같은데

 

파이썬처럼 permutation 함수가 있는지 찾아봤고, next_permutation이라는 함수가 있는 걸 발견했다

 

permutation을 통해 만들어진 numbers 수열을 1개, 2개,..., numbers크기 개 만큼 잘라서

만들어진 부분수열numbers set(set이라 중복 안됨)에 넣어서 업데이트 하는 방식을 사용해서 풀어야 하는 것 같다!

 

그리고 최종적으로 만들어진 set의 prime 여부를 판단해서 하나씩 쳐내고,

최종적으로 남은 prime의 개수를 return하면 되는 것 같다

 

python과 마찬가지로 set을 지원한다는 점이 편리하다

 

우선

set<int> uniqueNumbers;

이렇게 set을 만들어서 문자열을 모두 저장할 준비를 하자

 

그리고 아까 int로 바꾸면서 배열로 저장한 이유가 string에서 바로 sort같은 기능을 제공하지 않을 것 같아서였는데,

의외로 string을 sort하는게 가능하다

numbers 문자열을 sort해주자

sort(numbers.begin(), numbers.end());

 

이제 do-while문에서 작업해야 한다.

우선 next_permutation 함수를 통해 numbers 문자열에 들어있는 모든 원소를 사용해서 수열을 만들자

 

그리고 그 만들어진 수열에 대해 do문을 수행한다

길이 1부터 numbers.size()까지 순서대로 0부터 각 길이까지 끊는다

그리고 stoi()함수를 사용해서 string을 integer로 바꿔주고, 이 값을 아까 만들어둔 set uniqueNumbers에 집어넣자

 

다 만들고 나면 이제 소수인지 판별하자

int primeCount 변수를 만들어서 prime 여부가 충족될때마다 1씩 증가시키자

 

uniqueNumbers의 각 원소에 대해 for(int num:uniqueNumbers)

isPrime(num) 함수를 실행하자 (return값이 true false이므로 bool 함수이다)

 

isPrime(int num)

만약 1 이하이면 소수가 아니다

2이면 소수다

그 이상의 값에 대해서는 2부터 num의 제곱근 값까지 나눠본다

- 나눠 떨어지면 어떤 숫자의 배수라는 뜻이기 때문에 바로 false를 return한다

- 제곱근 값까지만 나눠보는 이유!

   어떤 수의 약수는 어떤 수의 제곱근 값을 기존으로 대칭이다. 따라서 절반만 판별하면 된다.

   예를 들어

        1*16=16

        2*16=16

        4*4=16

        8*2=16

        16*1=16

여기에서 루트16=4 값을 기준으로, 위 아래의 약수의 곱은 각 원소의 순서만 바뀐 형태임을 알 수 있음

전부 다 판별했는데도 false가 return되지 않았으면, 소수라는 뜻이기 때문에 true를 return한다

 

bool isPrime(int num) {
    if (num <= 1) return false; // 1 이하의 숫자는 소수가 아님
    if (num == 2) return true; // 2는 소수
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) return false; // 나누어떨어지면 소수가 아님
    }
    return true;
}

 

 

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

using namespace std;

// 소수 판별 함수
bool isPrime(int num) {
    if (num <= 1) return false; // 1 이하의 숫자는 소수가 아님
    if (num == 2) return true; // 2는 소수
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) return false; // 나누어떨어지면 소수가 아님
    }
    return true;
}

int solution(string numbers) {
    set<int> uniqueNumbers; // 중복을 피하기 위해 set 사용
    
    // 모든 가능한 순열 생성
    sort(numbers.begin(), numbers.end());
    do {
        for (int i = 1; i <= numbers.size(); i++) {
            int num = stoi(numbers.substr(0, i)); // 각 부분 순열로 숫자 생성
            uniqueNumbers.insert(num); // 중복되지 않도록 set에 추가
        }
    } while (next_permutation(numbers.begin(), numbers.end()));

    // 소수 개수 카운트
    int primeCount = 0;
    for (int num : uniqueNumbers) {
        if (isPrime(num)) {
            primeCount++;
        }
    }
    
    return primeCount;
}

 

 

작성 시작: 24.11.06. 10:35

작성 종료: 24.11.06 11:52

 

중간에 면접 관련 전화 받아서 시간이 좀 날라갔따..