< 프로그래머스 C++ > 소수 만들기

문제 설명

배열 nums에서 서로 다른 3개의 수를 골라 더했을 때 소수가 되는 경우의 개수를 구하는 문제이다.

항목	예시1	예시2
nums	[1, 2, 3, 4]	[1, 2, 7, 6, 4]
result	1	4

 

---

문제 해석

문제를 풀기 위해서 다음과 같은 핵심 포인트를 해결해야 한다.

 

1.  3개를 고르는 모든 조합 만들기
2.  합이 소수인지 판별하기

 

3개 조합은 3중 for문으로, 소수 판별은 별도 함수로 분리해서 해결했다.

---

문제 풀이

#include <vector>
#include <iostream>
#include <cmath>
using namespace std;

bool sosu(int num)
{
    if(num < 2) return false;
    for(int i = 2; i <= (int)sqrt(num); ++i)
    {
        if(num % i == 0) return false;
    }
    return true;
}

int solution(vector<int> nums) {
    int answer = 0;
    for(int i = 0; i < nums.size(); ++i)
    {
        for(int j = i+1; j < nums.size(); ++j)
        {
            for(int k = j+1; k < nums.size(); ++k)
            {
                int n = nums[i] + nums[j] + nums[k];
                if(sosu(n)) answer++;
            }
        }
    }
    return answer;
}

 

---

핵심 포인트

1. 소수 판별 함수

bool sosu(int num)
{
    if(num < 2) return false;
    for(int i = 2; i <= (int)sqrt(num); ++i)
    {
        if(num % i == 0) return false;  // 하나라도 나눠지면 소수 아님
    }
    return true;  // 끝까지 안 나눠지면 소수
}

소수란 1과 자기 자신으로만 나눠지는 수이다.

2부터 sqrt(n)까지 하나라도 나눠지면 false, 끝까지 안 나눠지면 true

 

sqrt까지만 확인하는 이유는, 약수는 항상 쌍으로 존재하기 때문이다.

예를 들어 36의 약수는 (2, 18), (3, 12), (4, 9), (6, 6) 이렇게 쌍인데, sqrt(36) = 6까지만 확인하면 나머지 쌍도 자동으로 계산이 가능하고, 시간복잡도도 O(N)에서 O(√N)으로 줄어들게 된다.

2. 3중 for문으로 모든 조합 만들기

for(int i = 0; ...)
    for(int j = i+1; ...)
        for(int k = j+1; ...)

j = i+1, k = j+1로 시작하면 중복 없이 모든 조합을 만들 수 있다.

nums 크기가 최대 50이라 가장 많이 돌아가는 경우의 수인 50번도

50C3 = 19,600번이라 3중 for문이어도 성능 문제 없다.

---

트러블슈팅

2중 for문 j에서 j+1로 세 번째 인자를 생성함

처음엔 3중 for문이 너무 무거운 것 같아서 2중 for문으로 해결하려 했다.
세 번째 숫자를 그냥 j+1로 고정하면 되지 않을까 하는 생각이었다.

// 처음 코드
for(int i = 0; i<nums.size(); ++i)
    for(int j = i+1; j<nums.size(); ++j)
        int a = nums[i] + nums[j] + nums[j+1];

이렇게 하면 세 번째가 항상 j 바로 다음 하나로 고정되어 버린다.

 

예시였던 nums = [1, 2, 7, 6, 4]로 확인해보자.

 

2중 for문 + j+1로 했을 때 나오는 조합

항목	1번째	2번째	3번째	4번째	5번째	6번째
i	0	0	0	1	1	2
j	1	2	3	2	3	3
세 번째 (j+1)	2	3	4	3	4	4
조합	(1,2,7)	(1,7,6)	(1,6,4)	(2,7,6)	(2,6,4)	(7,6,4)

6개만 나온다.

 

실제로 필요한 모든 조합 — 10가지

(1,2,7) (1,2,6) (1,2,4)
(1,7,6) (1,7,4)
(1,6,4)
(2,7,6) (2,7,4)
(2,6,4)
(7,6,4)

빠진 조합: (1,2,6), (1,2,4), (1,7,4), (2,7,4) 

4개나 빠졌다.

왜 빠질까?

j+1은 j 바로 다음 "하나" 만 본다.
근데 실제로는 j 다음 위치부터 끝까지 전부 탐색해야 한다.

// j+1 "하나"만
nums[j+1]

// j+1부터 끝까지 "전부"
for(int k = j+1; k < nums.size(); k++)
    nums[k]

---

정리

이 문제에선 다음을 배웠다.

• 조합을 만들 때 for문 하나를 줄이려다가 조합이 빠지는 실수를 할 수 있다.
• 우선 만들고, 최적화는 그 이후에 하기.

"for문 하나 줄이면 효율적이지 않을까?" 하는 생각이 있었는데, 이 경우엔 3중 for문이 맞았다
nums가 최대 50개라 조합 수가 많지 않으니까 성능 걱정은 필요 없었다