[프로그래머스] 소수 찾기 Level 2 [ JAVA ]

출처 : programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers                                                                  return

17	3
011	2

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다

풀이 - ( HashMap 사용 ver )

1. 모든 순열의 경우를 구하기. 
 * 주의 : 선택된 갯수를 1개 - (n-1) 개 까지 구해야하므로 for 문 필요 !  
 * 그런데 이렇게 하면, null 값이 발생함 .. ㅠ  ==> 3항 연산자로 해결했으나, 다른 분들은 ArrayList 로 해결.

2. 순열 중, 소수 개수 구하기.

주의 & 배운 점

1. String 으로 다루기 위해 charAt(i) + "";   // <-- "" 붙여줘야 했다.

2. String으로 저장됐음에도 Integer.parseInt( ) 메소드로 정수변환이 가능하다. ==> 011 == 11 판별 가능

3. 이후, 중복 값을 피하기 위해 해시 맵에 저장 ( 수열의 값 ) ==> 다른 사람은 ArrayList.contains 메소드 활용함.

4. 0 과 1 : 소수 아님 && 제곱근 값 까지만 나누어 떨어지는지 검색하면 된다. ( int sqrt = (int) Math.sqrt(n); )

코드 - HashMap

import java.util.*;
import java.util.Map.Entry;

class Solution {
    static boolean[] visited ;
    static String[] token;
    static String[] sel;
    static int answer ;
    static HashMap<Integer, Integer> hs;
    public int solution(String numbers) {
        answer = 0;
        visited = new boolean[ numbers.length()];
        token = new String[ numbers.length() ];
        sel = new  String [ numbers.length() ];
        hs = new HashMap<Integer, Integer>();
        
        for( int i=0 ; i< numbers.length(); i++){
            token[i] = numbers.charAt(i)+ "";
        }
        // 1. 순열구하기
        for( int i=1; i<= numbers.length(); i++){
            perm(0, token, i);
        }
        
       // perm(0, token);
        // 2. 각 순열 정수로 이어 붙여서 소수되는거 개수 세자.
        /*
        for( Entry<Integer, Integer> tmp : hs.entrySet()){
            System.out.println( tmp.getKey() + " value : " + tmp.getValue());
        }
        */
        L : for( Integer value : hs.keySet()){
            // 소수체크
            System.out.println(value);
            if ( value == 1 || value == 0) continue L ;
            for( int i=2; i<value; i++){
                if( value % i == 0 ) continue L ;
            }
            answer ++;
        }
        
        
        return answer;
    }
    private static void perm(int idx, String[] token, int s_idx){
        // 기저조건
        if ( idx == s_idx){
            // 순서대로 다 붙이고
            String test="";
            for( int i=0; i< visited.length; i++){
                test += sel[i] == null? "" : sel[i];
               
            }          
            hs.put( Integer.parseInt(test), hs.getOrDefault(Integer.parseInt(test), 1));            
            
            return;
        }
        
        for( int i=0; i<visited.length; i++){
            if ( !visited[i]){
                sel[idx] = token[i];
                visited[i] = true;
                perm(idx+1,token, s_idx);
                visited[i] = false;
            }
        }
        
    }
}

코드 - ArrayList

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.TreeSet;

class Solution {

	private TreeSet<String> set = new TreeSet<>();
	private int count;

	public static void main(String[] args) {

		String numbers = "11112";
		Solution s = new Solution();
		System.out.println(s.solution(numbers));

	}

	public int solution(String numbers) {

		int size = numbers.length();

		// 리스트에 담아줌
		List<Character> arr = new ArrayList<>();
		for (int i = 0; i < size; i++) {
			arr.add(numbers.charAt(i));
		}

		// 결과를 저장할 리스트
		List<Character> result = new ArrayList<>();

		// nPr에서 r을 계속 늘리면서 순열 알고리즘 수행
		for (int i = 0; i < size; i++) {
			permutation(arr, result, size, i + 1);
		}

		return count;
	}

	/**
	 * 소수 판별
	 * 
	 * @param n : 판별할 숫자
	 * @return
	 */
	private boolean isPrime(int n) {

		int i;
		int sqrt = (int) Math.sqrt(n);

		// 2는 유일한 짝수 소수
		if (n == 2)
			return true;

		// 짝수와 1은 소수가 아님
		if (n % 2 == 0 || n == 1)
			return false;

		// 제곱근까지만 홀수로 나눠보면 됨
		for (i = 3; i <= sqrt; i += 2) {
			if (n % i == 0)
				return false;
		}

		return true;
	}

	/**
	 * 순열 알고리즘
	 * 
	 * @param arr    : 원본 리스트
	 * @param result : 결과 담을 리스트
	 * @param n      : 전체 갯수
	 * @param r      : 선택할 갯수
	 */
	public void permutation(List<Character> arr, List<Character> result, int n, int r) {

		if (r == 0) {

			// 0으로 시작하는 부분집합은 제외
			if (result.get(0) != '0') {

				String str = "";
				int size = result.size();
				for (int i = 0; i < size; i++) {
					str += result.get(i);
				}

				int num = 0;

				// 이미 나온 숫자 조합이 아닐 경우
				if (!set.contains(str)) {
					num = Integer.parseInt(str);
					set.add(str);

					// 소수 판별
					if (isPrime(num)) {
						System.out.println(num);
						count++;
					}
				}
			}

			return;
		}

		for (int i = 0; i < n; i++) {

			result.add(arr.remove(i));
			permutation(arr, result, n - 1, r - 1);
			arr.add(i, result.remove(result.size() - 1));
		}

	}
}