[Java]프로그래머스 - 소수 찾기(lv.2)

 

프로그래머스

 

내 코드

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    private char[] charArr;
    private int cnt;
    private List<String> permutations = new ArrayList<>();
    
    public int solution(String numbers) {
        //1. String to charArray
        charArr = numbers.toCharArray();
        //2. 각 한자리 수가 소수인지 구함
        for(char c : charArr){
            int param = (int)c - 48;
            if(param>1&&isPrimeNumber(param)){
                cnt++;
            }
        }
        
        //3.순열구하기
        permutation(new int[charArr.length], new boolean[charArr.length], 0, charArr.length, charArr.length);
        //4.중복제거
        permutations = permutations.stream().distinct().collect(Collectors.toList());
        
        //5.순열 순회하며 소수인지 판단
        permutations.stream().forEach(e->{
                if(isPrimeNumber(Integer.parseInt(e))){
                    cnt++;
                }
            });
        
        return cnt;
    }
    
    private void permutation(int[] output, boolean[] visited, int depth, int n, int r){
        if(depth==r){
            //배열로 하니 초기화되던 것을 list로 바꾸니 정상적으로 저장됨 ㅅㅂ
            String[] newOutPut = Arrays.stream(output).mapToObj(Integer::toString).toArray(String[]::new);
            StringBuilder sb = new StringBuilder();
            Arrays.stream(newOutPut).forEach(e->sb.append(e));
            permutations.add(sb.toString());
            
                             
            return;
        }
        
        for(int i=0; i<n; i++){
            if(!visited[i]){
                visited[i]=true;
                output[depth]=(int)charArr[i]-48;
                permutation(output, visited, depth+1, n, r);
                output[depth]=0;
                visited[i]=false;
            }
        }
    }
    
    private boolean isPrimeNumber(int num){
        if(num==2){
            return true;
        }
        for(int i=2; i<num; i++){
            if(num%i==0){
                return false;
            }
        }
        
        return true;
    }
}

 

블로그 참고해서 다시 푼 코드

import java.util.*;

class Solution {
    //소수의 중복저장을 방지하기 위한 set사용
    private Set<Integer> set = new HashSet<>();
    
    //문자열로 주어진 수의 한자릿수 ~ n자릿수에서의 가능한 소수를 구하기 위한 함수
    public int solution(String numbers) {
        //i는 자릿수를 의미한다.
        for(int i=1; i<=numbers.length(); i++){
            dfs(1, new boolean[numbers.length()], i, new StringBuilder(), numbers);
        }
        
        return set.size();
    }
    
    //visited배열과 백트래킹을 사용하여 numbers에서 나올 수 있는 n자릿수(maxDepth) 소수를 구하는 재귀함수
    private void dfs(int depth, boolean[] visited, int maxDepth, StringBuilder sb, String numbers){
        if(depth>maxDepth){
            int number = Integer.parseInt(sb.toString());
            if(isPrimeNumber(number)){
                set.add(number);
            }
            
            return;
        }
        
        for(int i=0; i<numbers.length(); i++){
            if(!visited[i]){
                //백트래킹
                visited[i]=true;
                sb.append(numbers.charAt(i));
                dfs(depth+1, visited, maxDepth, sb, numbers);
                sb.deleteCharAt(sb.length()-1);
                visited[i]=false;
            }
        }
    }
    
    //들어온 수가 소수인지 판단하는 함수
    private boolean isPrimeNumber(int num){
    if(num<=1){
        return false;
    }
    if(num==2){
        return true;
    }
        
    for(int i=2; i<num; i++){
        if(num%i==0){
            return false;
        }
    }

    return true;
}
}

회고

처음에 dfs로 접근했을 때 visited배열을 사용할 생각을 못했고, dfs로 순서를 섞을 수 없다는 생각에 전체 순열을 구해 문제를 풀었다. 소수와 순열을 자바로 구현해본 적이 없어 찾아보면서 구현하는데 많은 시간이 걸렸고, set사용할 생각을 못해 stream의 distinct사용 코드를 봐가면서 풀었다. 결국엔 한자릿수, 문자열 길이만큼의 자릿수 소수만 판단하는 로직을 만들었고 그 외에 부분집합을 검증하지는 못해 오답처리를 받았다.

 

여튼 dfs, visited, 백트래킹, set을 사용하는 아이디어를 얻어 구현하게 됐는데 몇시간동안 끈질기게 한만큼 배운 점도 많았던 문제였다. 

 

새로 알게된 점

• 순열: nPn은 n!
• stream distinct() - 중복제거(중간 스트림)
• char타입의 숫자를 int로 변환할 경우 (int)ch - 48 해주면 된다. 아스키 코드의 48번부터는 56번까지는 0~9이다.

 

• StringBuilder엔 char타입도 append가능. 
• StringBuilder의 가장 마지막 요소를 지우고자할 땐 sb.deleteCharAt(sb.length()-1)