[Programmers] 소수 찾기
문제 출처 : [Programmers] 소수 찾기, https://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은 같은 숫자로 취급합니다.
💻코드
import java.util.ArrayList;
class Solution {
public int solution(String numbers) {
int answer = 0;
char[] c = numbers.toCharArray();
boolean[] visited = new boolean[10];
StringBuilder sb = new StringBuilder();
ArrayList<Integer> list = new ArrayList<>();
// 한 자리 수부터 문자열 길이에 해당하는 자리수까지 모든 순열을 구한다.
for(int i = 1; i <= c.length; i++){
permutation(c, sb, visited, list, 0, i);
}
// list에서 순서대로 값을 뽑고, 소수인 경우 answer 변수를 증가시킨다.
for(int i = 0; i < list.size(); i++){
if(isPrime(list.get(i))){
answer++;
}
}
return answer;
}
// 입력 문자열로부터 순열을 만들어주는 함수
static public void permutation(char[] c, StringBuilder sb, boolean[] visited, ArrayList<Integer> list, int depth, int target){
if(depth == target){
int num = Integer.parseInt(sb.toString());
// list에 해당 값이 존재하지 않는 경우에만 추가한다.
if(!list.contains(num)){
list.add(num);
return;
}
}
for(int i = 0; i < c.length; i++){
if(!visited[i]){
visited[i] = true;
sb.append(c[i] + "");
permutation(c, sb, visited, list, depth + 1, target);
visited[i] = false;
sb.delete(sb.length() - 1, sb.length());
}
}
}
// 매개 변수로 들어온 정수가 소수인지 판별해주는 함수
static boolean isPrime(int num){
if(num >= 0 && num <= 1){
return false;
}
for(int i = 2; i < num; i++){
if(num % i == 0){
return false;
}
}
return true;
}
}
💡후기
import java.util.ArrayList;
class Solution {
public int solution(String numbers) {
int answer = 0;
char[] c = numbers.toCharArray();
boolean[] visited = new boolean[10];
StringBuilder sb = new StringBuilder();
ArrayList<Integer> list = new ArrayList<>();
// 한 자리 수부터 문자열 길이에 해당하는 자리수까지 모든 순열을 구한다.
for(int i = 1; i <= c.length; i++){
permutation(c, sb, visited, list, 0, i);
}
// list에서 순서대로 값을 뽑고, 소수인 경우 answer 변수를 증가시킨다.
for(int i = 0; i < list.size(); i++){
if(isPrime(list.get(i))){
answer++;
}
}
return answer;
}
// 입력 문자열로부터 순열을 만들어주는 함수
static public void permutation(char[] c, StringBuilder sb, boolean[] visited, ArrayList<Integer> list, int depth, int target){
if(depth == target){
int num = Integer.parseInt(sb.toString());
// list에 해당 값이 존재하지 않는 경우에만 추가한다.
if(!list.contains(num)){
list.add(num);
return;
}
}
for(int i = 0; i < c.length; i++){
if(!visited[i]){
visited[i] = true;
sb.append(c[i] + "");
permutation(c, sb, visited, list, depth + 1, target);
visited[i] = false;
sb.delete(sb.length() - 1, sb.length());
}
}
}
// 매개 변수로 들어온 정수가 소수인지 판별해주는 함수
static boolean isPrime(int num){
if(num >= 0 && num <= 1){
return false;
}
for(int i = 2; i < num; i++){
if(num % i == 0){
return false;
}
}
return true;
}
}
이전 문제에서 순열과 조합 알고리즘을 구현해 보았는데, 신기하게도 바로 다음 문제에 순열을 이용하는 문제가 나왔다!😆 신기방기~
예전 같았으면 반복문으로 어떻게 경우의 수를 구해야 하나 고민했겠지만, 알고리즘을 직접 구현해 본 뒤로는 문제 해결 방식에 접근하는 속도가 훨씬 빨라졌다.😊😏
또 소수를 판별하는 데 있어서 저렇게 무식하게 구하지 않고 좀 더 효율적으로 찾아내는 방법이 여러 가지 있는데, 문제 유형이 브루트 포스로 되어있길래 그냥 완전 탐색으로 풀었다 ㅎㅎ.... 다행히도 입력 범위가 넓지 않아서 시간 초과가 나오지는 않은 것 같다!😅
부족한 CS
기초를 이렇게 PS
를 통해서 배워나가는 게 재밌고 기억에 더 오래 남는 것 같다. 앞으로도 꾸준히 화이팅!!😣
Author And Source
이 문제에 관하여([Programmers] 소수 찾기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jaeung5169/Programmers-소수-찾기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)