문제 92335. k진수에서 소수 개수 구하기

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/92335

프로그래머스

 

 

난이도 : Lv.2

 

문제 요약 설명

양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.

• 0P0처럼 소수 양쪽에 0이 있는 경우
• P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
• 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
• P처럼 소수 양쪽에 아무것도 없는 경우
• 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
  
  • 예를 들어, 101은 P가 될 수 없습니다.

정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.

입력

• 정수 n과 k

입력 제한

• 1 ≤ n ≤ 1,000,000
• 3 ≤ k ≤ 10

입력 예제

// input
437674 // n
3      // 3

// ans
3

 

풀이 방식

이 문제는 십진수로 표현된 n을 k진수로 변경하고, k진수로 표현된 수를 0으로 파싱했을 때 나오는 각 숫자(10진수로 취급) 중 소수를 찾는 것이 목적이다. 여기까지 이해를 했다면 다음으로 해야할 일들은 구현밖에 없으므로 비교적 간단하게 문제를 해결할 수 있다. 해결하는 방법은 다음과 같다.

 

십진수로 표현된 n을 k진수로 변경

  => 고전적인 방식을 사용한다. n을 반복적으로 k로 나눔으로써 각 자리수를 구해 배열 또는 문자열에 뒤집어서 저장하여  k진수로 표현된 수를 구한다.

 

k진수로 표현된 수를 0으로 파싱했을 때 나오는 각 숫자(10진수로 취급) 중 소수를 찾는다

=> 문자열이 있을 때 현재 숫자가 0이 아니라면 해당 숫자를 문자열 뒤에 추가, 0이라면 파싱이 되는 지점이므로 해당 문자열을 10진수로 변경하고 소수인지 판단한다. 소수 판단이 끝났다면, 문자열을 공백으로 초기화 한다.(이미 해당 소수 판단이 끝난 문자열이기 때문)

이 과정은 k진수의 수 끝까지 순회하며 계속 찾으며 소수의 개수를 구한다.

정답 코드 

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

using namespace std;

bool isPrime(long long num){
    if(num < 2) return false;
    
    for(int i = 2; i <= (int)sqrt(num); i++){
        if(num % i == 0){
            return false;
        } 
    }
    
    return true;
}

int solution(int n, int k) {
    int answer = 0;
    
    vector<int> v1;
    while(n > 0){
        v1.push_back(n % k);
        n /= k;
    }
    
    reverse(v1.begin(), v1.end());
    v1.push_back(0);
    
    string num = "";
    for(int i = 0; i < v1.size(); i++){
        cout << v1[i] << ' ';
        if(v1[i] != 0){
            num += to_string(v1[i]);
        }
        else{
            if(num.length() > 0){               
                answer += isPrime(stoll(num)) ? 1 : 0;
                //cout << num << " " << answer << '\n';
                num = "";
            }
            
        }
    }
           
    return answer;
}