문제풀이/알고리즘 문제 풀이

[ 프로그래머스 ] K진수에서 소수 구하기 (C++) - 수학

RealTone 2024. 4. 5. 15:09
728x90

🔗 문제 링크

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr


💡 문제 풀이 및 해석

  1. 일단 K진수를 구한다.
  2. 0을 기준으로 K진수를 split한다.
  3. split한 수들이 소수인지 판별하고, 소수이면 answer에 1을 더한다.

⭐️ 정답 코드 및 설명

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

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

int solution(int n, int k) {
    int answer = 0;
    string kNum="";

    while(n>=k){
        string i = to_string(n%k);
        n/=k;
        kNum+=i;
    }
    kNum+=to_string(n);
    reverse(kNum.begin(),kNum.end());

    vector<long> integer;
    string temp="";

    for(int i=0; i<kNum.size(); i++){
        char num = kNum[i];
        if(i == kNum.size()-1){
            temp+=num;
            integer.push_back(stol(temp));
            break;
        }
        if(num == '0'){
            if(temp=="") continue;
            integer.push_back(stol(temp));
            temp="";
            continue;
        }
        temp+=num;
    }

    for(long i : integer){
        if(isSosu(i)) answer++;
    }

    return answer;
}

🤔 문제 후기

int로 푸는 습관이 있다보니, long을 써야하는 부분을 알고 있었지만, 안고친 부분이 좀 많았다. 그래서 core dumped 오류가 계속 발생해도 이유를 찾지 못했다. 그리고 소수를 계산해야 하는데, 평소에는 아리토스테네스의 체를 사용해서 계산했는데, 그렇게하면 OutOfBounds오류가 날 수밖에 없기 때문에, 소수를 구해서 하는 문제가 아닌 숫자마다 소수인지 판별을 해야하는데, 이 점만 빠르게 캐치하면, 풀기에 어려운 문제는 아니였다.

728x90