소수 찾기

· 문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

---

· Thinking 1

[0, 1, 1] 인 경우 만들 수 있는 숫자
1. 011
2. 011
3. 101
4. 110
5. 101
6. 110

순열 사용....?..

 

public static int solution(String numbers) {
	int[] nums = new int[numbers.length()];
	ArrayList<String> temp = new ArrayList<String>();
		
	for (int i = 0; i < numbers.length(); i++) {
		nums[i] = Character.getNumericValue(numbers.charAt(i));
	}
		
	perm(nums, 0, nums.length, nums.length, temp);
	Collections.sort(temp);
	System.out.println(temp);
		
	for (int i = 1; i < temp.size(); i++) {
		if (temp.get(i-1).equals(temp.get(i))) {
			temp.remove(i);
		}
	}

	System.out.println(temp);

	int answer = temp.size();
		
	int i = 0;
	while (i < temp.size()) {
		for (int j = 2; j < Integer.parseInt(temp.get(i)); j++) {
			if (Integer.parseInt(temp.get(i)) % j == 0) {
				answer--;
				break;
			}
		}
		i++;
	}
		
	System.out.println(answer);
	return answer;
}
	
public static void perm(int[] arr, int depth, int n, int k, ArrayList<String> temp) {
	if (depth == k) {
		print(arr, k, temp);
		return;
	}
		
	for (int i = depth; i < n; i++) {
		swap(arr, i, depth);
		perm(arr, depth+1, n, k, temp);
		swap(arr, i, depth);
	}
}
	
public static void swap(int[] arr, int i, int j) {
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}
	
public static void print(int[] arr, int k, ArrayList<String> temp) {
	String str = "";
	for (int i = 0; i < k; i++) {
		if (i == k-1) {
			str += arr[i];
			temp.add(str);
		} else {
			str += arr[i];
		}
	}
}

17일 경우 1, 7, 17, 71 인데 이 코드는 순열이라서 17과 71만 나옴ㅎㅎ;

중복 순열로 풀어야하나보다..;;

---

· Thinking 2

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    public int solution(String numbers) {
        int[] nums = new int[numbers.length()];
		ArrayList<String> temp = new ArrayList<String>();

		for (int i = 0; i < numbers.length(); i++) {
			nums[i] = Character.getNumericValue(numbers.charAt(i));
		}

		for (int i = 1; i <= numbers.length(); i++) {
			perm(nums, 0, numbers.length(), i, temp);
		}
		Collections.sort(temp);

		for (int i = 1; i < temp.size(); i++) {
			if (temp.get(i - 1).equals(temp.get(i))) {
				temp.remove(i);
			}
		}

		for (int i = 0; i < temp.size(); i++) {
			if (temp.get(i).substring(0, 1).equals("0")) {
				temp.remove(i);
				i--;
			}
		}

		int answer = temp.size();

		int i = 0;
		while (i < temp.size()) {
			if (temp.get(i).equals("1")) {
				answer--;
			} else {
				for (int j = 2; j < Integer.parseInt(temp.get(i)); j++) {
					if (Integer.parseInt(temp.get(i)) % j == 0) {
						answer--;
						break;
					}
				}
			}

			i++;
		}

		return answer;
	}

	public static void perm(int[] arr, int depth, int n, int k, ArrayList<String> temp) {
		if (depth == k) {
			add(arr, k, temp);
			return;
		}

		for (int i = depth; i < n; i++) {
			swap(arr, i, depth);
			perm(arr, depth + 1, n, k, temp);
			swap(arr, i, depth);
		}
	}

	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	public static void add(int[] arr, int k, ArrayList<String> temp) {
		String str = "";
		for (int i = 0; i < k; i++) {
			if (i == k - 1) {
				str += arr[i];
				temp.add(str);
			} else {
				str += arr[i];
			}
		}
	}
}

정확성 : 66.7 ...

 

---

· 완성 코드

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    public int solution(String numbers) {
        int[] nums = new int[numbers.length()];
		ArrayList<String> temp = new ArrayList<String>();

		for (int i = 0; i < numbers.length(); i++) {
			nums[i] = Character.getNumericValue(numbers.charAt(i));
		}

		for (int i = 1; i <= numbers.length(); i++) {
			perm(nums, 0, numbers.length(), i, temp);
		}
		Collections.sort(temp);

		for (int i = 1; i < temp.size(); i++) {
			if (temp.get(i - 1).equals(temp.get(i))) {
				temp.remove(i);
                i--;
			}
		}

		for (int i = 0; i < temp.size(); i++) {
			if (temp.get(i).substring(0, 1).equals("0")) {
				temp.remove(i);
				i--;
			}
		}

		int answer = temp.size();

		int i = 0;
		while (i < temp.size()) {
			if (temp.get(i).equals("1")) {
				answer--;
			} else {
				for (int j = 2; j < Integer.parseInt(temp.get(i)); j++) {
					if (Integer.parseInt(temp.get(i)) % j == 0) {
						answer--;
						break;
					}
				}
			}

			i++;
		}

		return answer;
	}

	public static void perm(int[] arr, int depth, int n, int k, ArrayList<String> temp) {
		if (depth == k) {
			add(arr, k, temp);
			return;
		}

		for (int i = depth; i < n; i++) {
			swap(arr, i, depth);
			perm(arr, depth + 1, n, k, temp);
			swap(arr, i, depth);
		}
	}

	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	public static void add(int[] arr, int k, ArrayList<String> temp) {
		String str = "";
		for (int i = 0; i < k; i++) {
			if (i == k - 1) {
				str += arr[i];
				temp.add(str);
			} else {
				str += arr[i];
			}
		}
	}
}

음.. 풀긴 했는데.. 정말 풀기만 한 것 같다..

너무 복잡하게 풀었다ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

---

· 참고

- https://makefortune2.tistory.com/227

66. 조합, 중복조합, 순열, 중복순열 뼈대 알고리즘

- https://gorakgarak.tistory.com/522

순열(Permutation) 알고리즘

---

· 문제 출처

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

알고리즘 연습 - 소수 찾기 | 프로그래머스