[프로그래머스] 소수 만들기 - Java

소수 만들기 문제
https://programmers.co.kr/learn/courses/30/lessons/12977

문제설명

주어진 숫자 중 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을 만들 수 있습니다.

---

내 코드

import java.util.*;
class Solution {
    public int solution(int[] nums) {
        ArrayList<Integer> list = new ArrayList<>();
		
        // 세 숫자를 더한 수들을 list에 추가.
        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++){
                    list.add(nums[i] + nums[j] + nums[k]);
                }
            }
        }
		
        //  만약 소수이면 answer++;
        int answer = 0;
        for(int i = 0 ; i < list.size(); i++){
            int cnt = 0;
            for(int j = 1; j <= list.get(i) / 2; j++){
                if(list.get(i) % j == 0)
                    cnt++;
                if(cnt == 2)
                    break;
            }
            if(cnt == 1)
                answer++;
        }
        return answer;
    }
}

• 세 숫자를 더한 숫자들이 있는 list에서 해당 숫자를 1 ~ 해당 숫자의 반까지 나눴을 때 나머지가 0이면 cnt++을 해주었다.
• 만약 cnt >= 2 이면 1과 자신 외에도 나눠지는 숫자가 있다는 의미로 cnt == 2에서 break;를 하였고, cnt == 1이면 1과 본인 밖에 나눠지는 숫자가 없다는 뜻이기에 소수이므로 answer++를 해주었다.

알게된 점

• 처음에는 세 숫자를 더한 숫자가 중복되면 하나로 처리하는 줄 알고 HashSet를 통해 중복을 걸러냈었다. 하지만 몇몇 TC는 통과가 되었지만 대부분이 안되는 것을 확인한 후에 제한조건에 더한 숫자들의 중복을 걸러낸다는 말이 없었다는 것을 알았다. (제한 조건에 없는 내용에 대해 혼자 생각해서 조건을 만들지 말자!!!!!)

  ex)

  nums가 {1, 4, 5, 3, 6} 일 때 10이라는 숫자는 {1, 4, 5}와
  {1, 3, 6}을 통해 만들 수 있다. 이 때 두 가지 경우는 같은 10이라고 result에 +1이 되는 것이 아닌 +2가 되어야 한다.
  -> 같은 숫자여도 조합이 다르면 둘 다 취급!

• 원래 에라토스테네스의 체를 통해 풀려고 했지만 세 개의 숫자를 더한 것과 비교할 때 몇몇 TC에서 실패하여 계속 고민하다 위와 같은 코드로 풀게되었다. 물론 연습에서 알고리즘을 이용하여 푸는 것도 중요하지만 실전에서는 시간도 중요하기 때문에 계속 막히는 상황에 부딪혔을 때 다르게 생각하는 방법도 중요하다 느꼈다.(물론 이 문제를 통과한 이후에 에라토스테네스의 체로도 풀어보았다.)