[프로그래머스]K 진수에서 소수 개수 구하기

📒활용 개념

  1. 어떠한 수 n과 k에 대하여 n의 k진수로의 변환
  2. String split, Int to String, String to Int
  3. 어떠한 수 n의 소수 판단

📌문제설명

양의 정수n에 대하여 k진수로 바꿨을 때, 변환된 수 안에 조건에 맞는 소수가 몇 개인지 구하라.
조건

  • 0p0처럼 소수 양쪽이 0인경우
  • p0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무 것도 없는 경우
  • 0p처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무 것도 없는 경우
  • 단,p는 각 자릿수에 0을 포함하지 않는 소수

--> 결국 0을 기준으로 소수를 분리해라.

📌구현

#include <string>
#include <vector>
#include <stack>

using namespace std;

string number="0123456789ABCDEF";						//진수 표현 위한 num

string change (int num, int binary){					//진수 변환 함수(설명->활용개념 링크 참조)
    string result;
    if(num == 0){
        return "0";
    }
    while(num > 0){
        result = number[num % binary]+result;
        num /= binary;
    }
    
    return result;
}

bool check (long int dec){								//소수 확인 함수(설명->활용개념 링크 참조)
    if(dec<2){
        return false;
    }
    else{
        for(long int i=2; i*i<=dec; i++){
            if(dec%i==0){
                return false;
            }
        }
    }
    return true;
}

int solution(int n, int k) {
    int answer = 0;
    string s_total;										//진수변환과 int to string 이후 string
    string sum;
    vector<string> split;								//split이후 string
    
    s_total=change(n, k);
    
    for(int i=0; i<s_total.size(); i++){				//'0'을 기준으로 split
        if(s_total[i]=='0'){
            if(sum!=""){
                split.push_back(sum);
                sum="";
            }
        }
        else{
            sum+=s_total[i];
        }
    }
    
    if(sum!=""){										//왼쪽에만 0이 있는 경우 push_back
        split.push_back(sum);	
    }
    
    for(int i=0; i<split.size(); i++){					//split된 string 소수인지 확인
        if(check(stoll(split[i]))){
            answer++;
        }
    }
    
    return answer;
}

📌주의점

  • 문제를 읽고 사용해야하는 함수에 대한 흐름 파악.
  • n의 범위에 따라 stoi가 아닌 stoll사용.
  • 소수인지 파악.
  • 정확한 진수 변환.

좋은 웹페이지 즐겨찾기