12-11 TIL

주어진 배열에서 숫자 3개를 골라서 더했을 때 소수가 되는 경우의 개수를 구하는 문제를 풀어 보았다.

알고리즘을 설계할 때 항상 제일 단순하고 무식한 방법으로 접근해 보고 그렇게 테스트케이스를 통과한 이후에 점점 시간복잡도를 줄여 나가는 방식으로 진행하는 편이라 이번에도 거의 모든 경우를 탐색해보며 진행하였다.

for (int i = 0; i < nums.length; i++) {
                for (int j = i + 1; j < nums.length; j++) {
                    for (int k = j + 1; k < nums.length; k++) {
                        sumNums.add(nums[i]+nums[j]+nums[k]);
                    }
                }
            }

다음 코드로 먼저 주어진 배열에서 숫자 3개를 골라서 더한 값을 새로운 배열에 넣어주었고,

for(int num:sumNums){
                int flag=0;
                for(int i=2;i<=Math.sqrt(num);i++){
                    if(num%i==0){
                        flag=1;
                        break;
                    }
                }
                if(flag==0){
                    answer++;
                }
            }

다음 코드로 해당 배열에 들어있는 모든 수가 소수인지 일일이 확인하여 소수인 경우에는 answer값을 1씩 올려주어 해결했다.