프로그래머스 Level 2 : k진수에서 소수 개수 구하기 C언어

▶문제 : 코딩테스트 연습 - k진수에서 소수 개수 구하기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

▶코드 작성

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <math.h>//sqrt 제곱근 함수

char num[1000];
int len;

int primeNum(long long n) {//소수 판별 함수
    if (n == 0 || n == 1) return 0;
    for (long long i = 2; i <= (long long)sqrt(n); i++) {//n의 제곱근까지 반복
        if (n % i == 0) return 0;
    }
    return 1;
}

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

    while (n > 0) {//k진수로 변환
        num[len++] = n % k + '0';//num문자열에 반대로 대입
        n /= k;
    }

    long long digit = 0;//조건에 맞는 숫자 ex) 0220 -> 22
    for (int i = len - 1; i >= 0; i--) {//반대로 대입했으므로 뒤에서부터 시작
        if (num[i] == '0') {//k진수의 값이 0일 때
            if (primeNum(digit)) answer++;//소수 판별 후 개수 증가
            digit = 0;//초기화
        }
        else {
            digit *= 10;//k진수를 구할 때 반대로 구했으므로 10씩 곱하면서 자리수를 찾음
            digit += num[i] - '0';
        }
    }

    if (primeNum(digit)) answer++;//마지막에 구하지 못한 digit값 소수 판별

    return answer;
}

 

▶해석

코드를 짜는 순서는

1. 숫자 n을 k진수로 바꾸기

2. 소수 판별 함수 만들기

3. '0'사이의 숫자를 찾아서 소수 판별하기

이렇게 작성하였다.

 

1번은  k진수로 변환할 때 수가 길어질 수 있으므로 문자열을 사용해 대입하였다.

여기서 쉽게 대입하기 위해 구하는 순서대로 대입하여 실제 k진수와 반대로 대입하였다.

 

2번 소수 판별 함수는 매개변수 n을 2부터 n의 제곱근까지 모두 나누어 딱 떨어지지 않으면 소수로 판별하였다.

 

3번은 num문자열을 처음 대입할 때 반대로 대입해서 i를 len-1부터 시작하였다.

num [i]이 '0'이 아닌 숫자면 반대로 대입한 부분을 고려하여 10을 곱하면서 값을 더하고

num [i]이 '0'이면 '0'과 '0'사이의 숫자를 구한 digit값을 소수 판별하여 개수를 구한다.