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

문제

주어진 종이조각을 조합해서 만들 수 있는 소수의 갯수를 구하는 문제이다.

풀이

이런 문제는 모든 경우를 살펴봐야는 완전탐색 문제이다. 자바는 파이썬과 다르게 Combination 라이브러리가 존재하지 않기 때문에, 만들 수 있는 모든 숫자의 경우를 살펴보기 위해선 BackTracking을 사용해야 한다.

순열과 조합을 구하는 문제는 BackTracking을 이용하여 푼다.사실 완전 탐색과 백트래킹은 모든 경우를 탐색한다는 점에서 매우 유사하며, 사실상 코트 테스트에서 같은 풀이를 사용한다.

모든 길이의 숫자에 대해 탐색을 진행하는 중간에, 문자열을 Int로 바꾸어 리스트에 중복 없이 담아서, 마지막에 소수인 숫자의 갯수를 해주는 방식으로 구현하였다.

• DFS방식을 사용. 조합을 구하는 문제
• visited 배열을 통해 현재 숫자가 추가 되어 있는지 없는지 판단
• List 배열에 중복없이 만든 값을 담아 놓음
• isPrimeNum() 함수를 통해 소수 여부 판단

아래 코드를 보면 더 이해가 잘 될 것이다.

코드

import java.util.*;
class Solution {
    public List<Integer> list = new ArrayList<>();
    public boolean[] visited = new boolean[7];


    public int solution(String numbers) {
        int answer = 0;
        for (int i = 0; i < numbers.length(); i++) {
            dfs(numbers, "", i+1);
        }
        for (int x : list) {
            if (isPrimeNum(x)) {
                answer++;
            }
        }
        
        return answer;
    }

    public void dfs(String str, String temp, int length) {
        
        if (temp.length() == length) {
            int num = Integer.parseInt(temp);
            if (!list.contains(num)) {
                System.out.println(num);
                list.add(num);
            }
        }

        for (int i = 0; i < str.length(); i++) {
            if (!visited[i]) {
                visited[i] = true;
                temp += str.charAt(i);
                dfs(str, temp, length);
                visited[i] = false;
                temp = temp.substring(0, temp.length()-1);
            }
        }
    }
    
    public boolean isPrimeNum(int x) {
        int i = 2;
        if (x < 2) return false;

        while (i * i <= x) {
            if (x % i == 0) {
                return false;
            }
            i++;
        }
        return true;
    }
}