C# 소수 만들기 - 프로그래머스 [Lv.1]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/12977

 

 

 

나의 풀이

using System;
using System.Collections.Generic;

class Solution
{
    public int solution(int[] nums)
    {
        int answer = 0;
        
        for(int a = 0; a < nums.Length; a++)
        {
            for(int b = 0; b < nums.Length; b++)
            {
                if(a <= b) continue;
                for(int c = 0; c < nums.Length; c++)
                {
                    if(b <= c) continue;
                    if(a == c) continue;
                    
                    if(IsPrime(nums[a] + nums[b] + nums[c])) 
                        answer++;
                }
            }
        }
        
        return answer;
    }
    
    private bool IsPrime(int n)
    {
        if(n <= 1) return false;
        for(int i = 2; i * i <= n; i++)
        {
            if(n % i == 0)
                return false;
        }
        return true;
    }
}

처음에 합만 먼저 HashSet에 넣어서 반복문으로 소수체크했는데, 그러니까 통과못하는 케이스가 존재

1 + 2 + 5 = 7 이랑

1 + 3 + 4 = 7 이 두개를 다른 경우로 카운트 해야한다.

그런데 1, 2, 5랑 1, 5, 2는 같은 경우로 카운트 해야한다.

 

 

다른사람 풀이

using System;

class Solution
{
    public bool IsPrime(int num)
    {
        if(num <= 1)
            return false;

        for (int i = 2; i < num / 2; i++)
        {
            if(num % i == 0)
                return false;
        }

        return true;
    }

    public int solution(int[] nums)
    {
        int answer = 0;

        for(int i = 0; i < nums.Length - 2; i++)
        {
            for(int j = i + 1; j < nums.Length - 1; j++)
            {
                for(int k = j + 1; k < nums.Length; k++)
                {
                    if(IsPrime(nums[i] + nums[j] + nums[k]))
                        answer++;
                }
            }
        }

        return answer;
    }
}

for문 중첩시 i + 1 부터 시작하는 아이디어가 좋은듯.