어떤 수를 서로 다른 소수 3개의 합으로 표현하는 경우의 수

 프로그래머스 사이트에서 웹 개발자 리모트 잡페어 알고리즘 테스트를 보았다. 그리고 부끄럽게도 2시간동안 한 문제도 완벽하게 풀 지 못했다. 

 비록 알고리즘을 따로 공부하지 않았지만 참으로 부끄러울 수 밖에 없다.

 3일이 지난 후에 정리르 하며 돌아보니 어리석게도 문제를 제멋대로 해석한 것을 가장 큰 잘못이라 생각한다.

 1번문제는 어느 수를 서로다른 소수 3개의 합으로 표현하는 경우의 수를 구하는 문제이다. 그런데 나는 이 문제를 주어진 수를 소수들의 합으로 만들어지는 경우의 수로 이해하였다. 3개가 아닌...

 때문에 소수 3개라면 반복문 3번으로 쉽게 해결 될 문제지만 100이하의 소수만 하여도 25개가 되기 때문에 조합의 수는 소수의  n! -@(간단하게 넣을 수 있는 제약조건)로 무궁무진하다. 

 나는 이 문제의 접근을 주어진 수 이하의 소수 구하기. 그들의 합으로 주어진 수 조합해보기로 풀려고 하였다. 소수구하는 알고리즘은 간단하게 만들었다.

static boolean IsPrime(int number)

{

    for(int checkPrime = 2; checkPrime < number; checkPrime++)

    {

        if( (number % checkPrime) == 0)

        {

            return false;

        }

    }

    return true;

} 

자신보다 작은숫자까지 나누어 떨어지면 소수가 아닌것으로 판별하였다. 그리고 이걸 arraylist 에 추가하여 소수들의 배열을 만들었다.

그리고 이걸통해 조합을 하면되는데 3개의 합이라면 for 문3개로 해결될 문제인데.... 나는 3개라는 것을 파악하지 못하여 재귀함수를 구현하려고 끙끙대려다 결국 포기하였다.

이런 실수가 일어나지 않도록 알고리즘테스트를 틈틈히 하고 잔 실수를 줄여야겠다.

3개의 합으로 구하는 간단한 3중 포문으로 해결방법이다.

다음은 구현하려고 했던 전 구간 재귀함수를 통한 방법을 통해 풀어봐야겠다. 검색도중 2비트로 나눠 구하는 것이 있었는데 이 방법도 짧게 작성이 가능할 것 같아  좋아보였다 단지. 13개의 조합이라면 2^13. 괜찮을지 의문이다.

아래는 풀이이다.

  public static int solution(int number) {

      int answer = 0;

      ArrayList<Integer> primeGroup =  new ArrayList<Integer>();

     

      for (int i = 2; i < number; i++) {

if(IsPrime(i)){

System.out.println(i);

primeGroup.add(i);

}

}

     

        int[] arr = new int[primeGroup.size()];

        for (int i = 0; i < arr.length; i++) {

arr[i] = primeGroup.get(i);

}

        

        

        for (int i = 0; i < arr.length; i++) {

        for (int j = i+1; j < arr.length; j++) {

                 for (int j2 = j+1; j2 < arr.length; j2++) {

                System.out.println("a b c 확인"+arr[i]+""+arr[j]+""+arr[j2]);

if(number==(arr[i]+arr[j]+arr[j2])){

System.out.println("a b c 확인"+arr[i]+""+arr[j]+""+arr[j2]);

answer++;

}

}

}

}

System.out.println(answer);

        

        return answer;