[프로그래머스] - 소수 만들기(C#)

소수 만들기

오늘은 Summer/Winter Coding(~2018) 에 출제 되었던 "소수만들기" 문제를 풀어보도록 하겠습니다. 바로 문제를 살펴보도록 하겠습니다.

 

문제 설명

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

 

제한 사항

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

 

입출력 예

nums	result
[1, 2, 3, 4]	1
[1, 2, 7, 6, 4]	4

 

입출력 예 설명

입출력 예 #1
[1,2,4]를 이용해서 7을 만들 수 있습니다.

입출력 예 #2
[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.

 

시작 코드

using System;

class Solution
{
    public int solution(int[] nums)
    {
        int answer = -1;

        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        System.Console.WriteLine("Hello C#");

        return answer;
    }
}

 

나의 풀이

using System;

class Solution
{
    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++)
                {
                    int n = nums[i] + nums[j] + nums[k];
                    int cnt = 0;
                    
                    for(int t = 2; t <= n; t++)
                    {
                        if(n % t == 0) { cnt++; }
                    }
                    if(cnt == 1) answer++;
                }
            }
        }
        return answer;
    }
}

 

코드 분석

int형 배열 nums가 주어지며 코드가 시작됩니다. 처음에 -1로 초기화 되어있던 answer를 0으로 바꿔주고, 4중 for문을 작성해줍니다. 첫번째부터 세번째 for문 까지는 각 상위 for문의 시작지점(i = 0)과 종료지점(nums.Length - 2)에 1을 더한 값으로 시작하도록 하였습니다. 세번째 for문 안에서 int형 n을 선언하고, for문을 거쳐 나온 nums[i], [j], [k]를 전부 더해 넣어줍니다. int형으로 cnt를 선언해주고, 마지막 for문을 돌립니다. t = 2부터 t가 n보다 작거나 같아질 때까지 돌리며 그 안에는 if문이 존재합니다. n을 t로 나눈 나머지가 0이라면 cnt를 증가시켜주고 for이 종료되면 다시 if문을 만나 cnt가 1이면 answer의 값을 증가시켜 줍니다. 모든 과정이 종료되고 answer값을 최종적으로 리턴하며 코드가 끝이 납니다.

 

풀이 설명

문제를 풀기 위해서는 소수가 무엇인지부터 확실히 알아야 합니다. 소수는 쉽게말해서 1과 본인으로만 나눠질 수 있는 수를 말합니다. 예시에서 나왔듯이 "7"같은 수가 소수입니다. 문제에서 원하는 것은 간단합니다. 주어진 nums배열에서 숫자 3개를 뽑아서 더했을 때, 소수가 될 수 있는 가짓수가 몇개인지를 구하는 것입니다. 앞에서 실행하는 삼중for문은 nums배열에서 겹치지 않는 3개의 숫자를 뽑기 위한 것입니다. 그렇게 뽑은 값을 더한 것이 n이고, 네번째 for문은 소수를 판단하기 위한 것으로 1을 제외한 t = 2부터 시작해서 n까지 나눈 나머지가 0이라면 즉, n이 나누어 떨어진다면 cnt를 증가시키고 만약 나누어 떨어진 횟수가 1번이라면 소수로 판단하여 answer를 증가시켜 주는 것입니다.

 

<NEXT>

오늘은 Summer/Winter Coding(~2018)에 출제된 "소수만들기" 문제를 풀어보았습니다. 게임개발을 하다보니 for문과 if문을 많이 겹쳐서 쓰는 것을 꺼리게 되지만, 중첩반복문은 어디서나 많이 쓰이는 것 같습니다. 다음에는 소수 만들기를 했으니 "소수 찾기" 문제를 다뤄보도록 하겠습니다. 감사합니다.