[프로그래머스][Java][Lv. 2] 소수 찾기

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/42839

---

제한 사항

---

입출력 예

---

풀이

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

class Solution {
    private ArrayList<String> nums = new ArrayList<>();
    private HashSet<Integer> result = new HashSet<>();
    private int num_len;
    
    public int solution(String numbers) {
        int answer = 0;
        num_len = numbers.length();
        
        for (int i = 0; i < num_len; i++)
            nums.add(numbers.substring(i, i + 1));
        for (String strNum : nums)
            result.add(Integer.valueOf(strNum));
        
        for (int i = 0; i < numbers.length(); i++) find(Set.of(i), nums.get(i));
        
        for (Integer num : result) answer += isPrime(num);
        
        return answer;
    }
    
    private void find(Set<Integer> paramIndexes, String num) {
        for (int i = 0; i < nums.size(); i++) {
            HashSet<Integer> indexes = new HashSet<>();
            indexes.addAll(paramIndexes);
            if (indexes.contains(i)) continue;
            
            String strNum = num + nums.get(i);
            result.add(Integer.valueOf(strNum));
            indexes.add(i);
            if (strNum.length() < num_len) find(indexes, strNum);
        }
    }
    
    private static int isPrime(int num) {
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) return 0;
        }
        return (num > 1) ? 1 : 0;
    }
}

---

후기

소수를 찾는 로직은 관련 문제가 많아서 어렵지 않지만 숫자를 조합할 때 이미 찾은 인덱스를 제외하는 로직이 이 문제의 핵심이라고 할 수 있다. 맞는거 같은데 처음에 몇 번 틀려서 도대체 뭐 때문이지 생각해보니까 find() 안의 indexes를 반복문 바깥에다 선언해놔서 재귀 함수가 끝나고 다시 해당 부분으로 돌아왔을 때 이전의 인덱스 기록이 공유돼서 그런거였다;;

그나저나 문제를 자주 안 푸니까 2단계 정답률 높은순인데도 뭔가 풀기가 힘들어졌다... 어려워도 꾸준히 풀 수 있도록 노력해야겠다.