[프로그래머스 C#] Lv.2 k진수에서 소수 개수 구하기

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

- 코드참조 ( 진수변환 -> 0을 기준으로 숫자 추출 -> 소수체크 )

 

+ 만약 테스트 1번만 시간초과가 뜬다면 소수를 체크하는 부분에서 최적화가 이루어지지 않았기 때문일 확률이 높다.

https://godgjwnsgur7.tistory.com/85

[C#] 소수 판별 최적화 알고리즘

 

+ StringBuilder이 아닌 string으로 사용해도 시간초과는 뜨지 않지만, 문자열 내의 추가, 삭제 등이 많이 이루어진다면 StringBuilder를 사용하는 것이 좋다. // 테스트 1번 기준 2~3초 차이

https://godgjwnsgur7.tistory.com/66

[C#] StringBuilder VS String 연산 성능 비교

    using System;
    using System.Text;

    public class Solution
    {
        public int solution(int n, int k)
        {
            int answer = 0;
            long num = 0;
            StringBuilder sb = new StringBuilder();

            // 1. 진수변환
            while (n != 0)
            {
                sb.Insert(0, (n % k).ToString());
                n /= k;
            }
            // 2. 0을 기준으로 숫자를 추출
            for (int i = 0; i < sb.Length; i++)
            {
                if (sb[i] != '0')
                {
                    num *= 10;
                    num += (long)sb[i] - '0';
                }
                else
                {
                    if (Function(num))
                        answer++;
                    num = 0;
                }
            }
            // 예외처리
            if (Function(num))
                answer++;
                
            return answer;
        }

        // 소수 체크 함수
        public bool Function(long num)
        {
            if (num < 2)
                return false;

            for (int i = 2; i <= Math.Sqrt(num); i++)
                if (num % i == 0)
                    return false;

            return true;
        }
    }