내일배움캠프 43일차 TIL

14 Sep 2023

Reading time ~3 minutes

오늘 배운 내용

계산해야할 정수의 최대 크기로 알맞는 자료형 정하기
필요한 데이터만 계산하기

nbcbanner

계산해야할 정수의 최대 크기로 알맞는 자료형 정하기

프로그래머스 k진수에서 소수 개수 구하기

문제를 풀며 알게 된 내용이다.

문제는 주어진 수를 k진수로 변환하고 그 값을 0을 기준으로 분리해서

나온 수의 배열에 대해 소수(prime)의 갯수를 구하는 문제였다

일단 먼저 십진수를 k진수로 바꾸고 0을 기준으로 분리하는 메서드를 만들었다.

public int[] SplitKNumber(int n, int k)
    {
        string str = "";
        
        while(n != 0)
        {
            str += n % k;
            n /= k;
        }
        
        char[] charArr = str.ToCharArray();
        Array.Reverse(charArr);
        
        str = new string(charArr);
        // ToString이 아니라 new string을 해야됨
        
        string[] strArr = str.Split("0");
        List<int> list = new List<int>();
       
        for(int i =0; i< strArr.Length; i++)
        {
            int temp;
            if (int.TryParse(strArr[i], out temp))
            {
                list.Add(temp);
            }
        }
        
        // 빈 list를 ToArray()하면 런타임 에러?
        
        return list.Count == 0 ? new int[1] :list.ToArray();
        
    }

그런데 대부분의 테스트 케이스를 통과했지만 테스트 케이스 1번을 통과할 수 없었고

계속 고민을 하다가 결국 항복하고 프로그래머스에 있는 힌트를 봤다.

1번 케이스가 틀린 이유는 정수형을 int로 저장했기 떄문이었는데,

이 문제에서는 885733은 3진법으로 1122222222221 같이 int의 범위를 벗어난 케이스가 나올 가능성이 있기 때문에

List으로 List를 선언 해서 사용했어야 됬다.

 public long[] SplitKNumber(int n, int k)
    {
        string str = "";
        
        while(n != 0)
        {
            str += n % k;
            n /= k;
        }
        
        char[] charArr = str.ToCharArray();
        Array.Reverse(charArr);
        
        str = new string(charArr);
        // ToString이 아니라 new string을 해야됨
        
        string[] strArr = str.Split("0");
        List<long> list = new List<long>();
       
        for(int i =0; i< strArr.Length; i++)
        {
            long temp;
            if (long.TryParse(strArr[i], out temp))
            {
                list.Add(temp);
            }
        }
        
        // 빈 list를 ToArray()하면 런타임 에러?
        
        return list.Count == 0 ? new long[1] :list.ToArray();
        
    }

이렇게 수정했지만 오히려 문제가 더 커졌다

테스트 케이스 2개가 런타임 오류를 발생시켰고 해당부분도 비슷하게

계산해야되는 정수형의 크기가 너무 커서 발생한 오류 였다.

필요한 데이터만 계산하기

나는 처음에 소수를 구하는 부분에서

배열에 있는 수들중 가장 큰수를 구해서 해당 수 까지의 소수여부를

에라스토테네스의 체로 판별한 bool배열을 통해서 소수를 판별했다.

public bool[] primeCheck(long max)
    {
        bool[] isNotPrime = new bool[max+1];
        isNotPrime[0] = true;
        if (isNotPrime.Length  <2) return isNotPrime;
        isNotPrime[1] = true;
        if (isNotPrime.Length  <3) return isNotPrime;
        
        
        
        for(long i=2; i< Math.Sqrt(isNotPrime.Length); i++)
        {
            // 해당 수가 소수인지 판별하려면
            // 2~제곱근 까지의 수로 나눴을때
            // 나누어 떨어지지 않는다면 소수임
            
            
            if (!isNotPrime[i])
            {
                for(long j = 2; j *i< isNotPrime.Length; j++)
                {
                    isNotPrime[j*i] = true;
                }
            }
        }
        
        return isNotPrime;
    }

하지만 여기서 max가 어느정도 크기까지는 감당할 수 있었지만

아까와 같이 int를 벗어나는 큰수까지의 prime을 구해야되는 경우에 너무 많은 계산을 하게되어서

오버플로우가 발생했다.

이 문제를 해결한 방법은 해당 문제에서 각각의 수는 long 타입을 써야할 정도로 큰수지만

수의 갯수는 사실 그렇게 많지 않았다. 그래서 모든 수의 prime을 따로 구하지 않고

배열에 있는 수의 Prime 여부만을 체크하도록 함수를 다시 만들었다.

 public bool PrimeCheck(long number)
    {
        if( number < 2){
            return false;
        }
       int sqrt = (int)Math.Sqrt(number);
        bool result = true;
        
        for (long i = 2; i<= sqrt; i++)
        {
            if (number % i ==0 )
            {
                result = false;
                break;
            }
        }
        return result;
    }
}

이렇게 계산 횟수를 줄여서 문제를 해결할 수 있었다.

결국 문제에서 요구하는 답을 찾는데 꼭 필요한 데이터가 무엇인지를 잘 생각해야

제한된 시간안에 문제를 해결할 수 있다는 것을 깨달을 수 있었다.