소수 만들기 - 프로그래머스 Lv.1

Justin·2022년 8월 5일

알고리즘 풀이

목록 보기

6/7

문제 설명

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

출력 예시

간단 설명

int형 배열이 주어지고, 배열 내에 주어진 수 3가지를 조합하여 몇 개의 소수를 만들 수 있는지 구하는 문제이다.

문제 해결방법

소수란?
1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수이다. 예를 들어 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 등이 있다.

그럼 소수를 어떻게 구할 수 있을까?

IsPrime()소수 인지 아닌지 체크 하는 함수를 제작한다. 이는 간단하게 1과 자기자신 이외에 추가로 나눠지는 수가 있다면 false 값을 리턴 하는 구조이다.

public bool IsPrime(int num)
        {
            int checkNum = (int)Math.Sqrt(num);
            for (int i = 2; i <= checkNum; i++)
            {
                if (num % i == 0)
                    return false;
            }

            return true;
        }

다만 여기서 불필요한 계산을 줄이기 위해 int checkNum = (int)Math.Sqrt(num) 를 사용했다.

소수인지 체크 할 때는 제곱근 만큼만 비교해보면 알 수 있다. 자세한 내용은 검색해보면 많이 나온다.

3가지 수 비교하기

일단 이 문제는 배열 내에 주어지는 3가지의 경우의 수를 모두 구하고 더해야하기에 무식하게 모두 찾아보는 방안을 활용하고자 했다.

처음에 list에 넣고 더하고 쑈를 하다가 아주 간단한 방법을 찾아 그렇게 진행했다.

public int solution(int[] nums)
        {
            int answer = 0;
            // 3가지의 수를 구해야하니 3가지 수를 지속 탐색

            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++)
                    {
                        int sum = nums[i] + nums[j] + nums[k];
                        if (IsPrime(sum))
                            answer++;
                    }

            return answer;
        }

코드 해석

처음에 이해가 안가서 찾아 봤을 때 대부분 코드만 적어두고 설명이 없어 나와 같은 초보자를 위해 하나하나 설명하겠다.

첫 라인

먼저 처음 for문은 가장 처음 부터 시작하여 길이보다 -2인 만큼 까지만 진행한다.

왜냐면 3가지의 수를 더 해야하는데, 남은 배열의 숫자가 3가지가 되지 않다면 비교할 수가 없다.

for (int i = 0; i < nums.Length - 2; i++)

두 번째 라인

다음은 위의 for문 보다 하나 뒤에 수 부터 시작해서 마찬가지로 3가지 수 조합을 해야하기에 -1까지만 반복을 한다.

for (int j = i + 1; j < nums.Length - 1; j++)

세번째 라인

마지막 for 역시 j를 사용한 for문의 다음 즉 3번째 배열을 사용하기 위해 j+1 부터 시작해서 배열의 마지막 까지 반복한다.

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

이제 여기서 3가지의 수 nums[i], nums[j], nums[k]를 모두 더해서 위에서 만든 소수 체크를 통해 소수하면 answer를 증가 시키는 방안을 사용한다.

이렇게 3가지의 수를 계속 비교 시키면 입출력의 예로 활용한 int[] tem = {1,2,7,6,4 } 가 주어졌을 때 아래와 같이 3가지의 수를 지속적으로 찾아보며 소수인지 찾는 과정을 거친다.

1, 2, 7
1, 2, 6
1, 2, 4 => 7. 소수 
--- int j를 사용한 for문의 j 값 증가
1, 7, 6
1, 7, 4
--- int j를 사용한 for문의 j 값 증가
1, 6, 4 => 11. 소수
--- int i를 사용한 for문의 i 값 증가
2, 7, 6
2, 7, 4 => 13. 소수 
--- int j를 사용한 for문의 j 값 증가
2, 6, 4
--- int i를 사용한 for문의 i 값 증가
7, 6, 4 => 17. 소수