[Programmers / Level 2] 42839. 소수 찾기 (Java)

💡 Info

• 난이도: Lv2
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42839
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/2/소수 찾기

입출력 조건

입출력 예시

문제 이해

• 문자열 중 소수의 개수를 구하면 되는 문제
  • 백트래킹 사용

알고리즘

풀이 시간 : 37분

• 1자리부터 n자리까지의 조합 만들기
  • 모든 조합을 HashSet에 저장해서 중복 없애기
• HashSet에 저장된 숫자 중 소수만 카운트 -> 소수 개수 반환

import java.util.*;

class Solution {
    public int solution(String numbers) {
        Set<Integer> uniqueNumbers = new HashSet<>();
        boolean[] visited = new boolean[numbers.length()];

        for (int i = 1; i <= numbers.length(); i++) {
            generateCombinations(numbers, "", i, visited, uniqueNumbers);
        }

        int answer = 0;
        for (int num : uniqueNumbers) {
            if (isPrime(num)) {
                answer++;
            }
        }
        return answer;
    }

    public void generateCombinations(String str, String current, int length, boolean[] visited, Set<Integer> uniqueNumbers) {
        if (current.length() == length) {
            uniqueNumbers.add(Integer.parseInt(current));
            return;
        }

        for (int i = 0; i < str.length(); i++) {
            if (!visited[i]) {
                visited[i] = true;
                generateCombinations(str, current + str.charAt(i), length, visited, uniqueNumbers);
                visited[i] = false;
            }
        }
    }

    public boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

결과