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

문제 설명

 

프로그래머스

 

접근 방법

해당 문제에서는 임의의 숫자 문자열이 주어졌을 때 각각의 숫자로 만들 수 있는 수 중 소수의 개수가 몇 개인지를 요구하고 있다.

 

우선 주어진 숫자 문자열을 토대로 만들 수 있는 모든 경우의 수를 탐색하도록 했는데, 이때 백트래킹을 이용했다.

 

이후 백트래킹을 통해서 만들 수 있는 수를 탐색하면서 해당 수가 소수인지를 판별하도록 했다. 다음은 특정 수가 소수인지를 판별하는데 사용했던 로직이다.

 

    private boolean isPrime(int n) {
        if (n < 2) {
            return false;
        }

        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }

        return true;
    }

 

판별이 끝나면 해당 수를 HashSet에 추가시켜주었는데, 이는 탐색 과정에서 중복으로 탐색하는 경우도 발생할 수 있기 때문이다. 최종적으로 HashSet의 크기를 반환해주었다.

 

 

전체 소스 코드

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

class Solution {

    Stack<Character> findValue = new Stack<>();
    Set<Integer> result = new HashSet<>();
    char[] chars;
    int length;

    public int solution(String numbers) {
        chars = numbers.toCharArray();
        length = chars.length;
        boolean[] visited = new boolean[length];
        find(visited);

        return result.size();
    }

    private void find(boolean[] visited) {

        StringBuilder sb = new StringBuilder();
        int value;

        for (int i = 0; i < length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                findValue.push(chars[i]);

                for (Character character : findValue) {
                    sb.append(character);
                }

                value = Integer.parseInt(sb.toString());

                if (isPrime(value)) {
                    result.add(value);
                }

                sb.setLength(0);

                find(visited);

                findValue.pop();
                visited[i] = false;
            }
        }
    }

    private boolean isPrime(int n) {
        if (n < 2) {
            return false;
        }

        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }

        return true;
    }
}

 

 

참고자료

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