프로그래머스 알고리즘 (java)
소수 찾기
코드 리뷰
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하는 문제입니다.
조건
- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0~9까지 숫자만으로 이루어져 있습니다.
- "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
- ex) 013, 031, 3, 1, 10, ... 등 뽑을 수 있는 모든 경우가 가능
풀이 방향
저는 맨 처음 조합으로 풀면 될 것이다 생각했습니다. 그래서 조합을 구하는 제귀 메소드와 소수를 판별하는 메소드를 조합하면 될 것 이라 예상했습니다.
하지만 조합으로 풀면 순서를 생각 하지 않습니다. 1,3 을 뽑으면 13 과 31 이 되는데 그걸 예상 못해서 오래 고민했습니다.
결국
String을char[]로 Parsing 한다.- parsing 한
char[]를 만들 수 있는 순열을 모두 구한다. - 구하면서 소수인 것은
list에 담는다. list의 size를 return 한다.
으로 풀면 될것이다 생각하고 풀어 봤습니다.
메인 로직
import java.util.HashSet;
import java.util.Set;
public class FindSosu {
public int solution(String numbers) {
char[] list = numbers.toCharArray();
int[] combArr = new int[list.length];
for (int i = 0; i < list.length; i++) {
combArr[i] = Integer.parseInt(String.valueOf(list[i]));
}
Set<Integer> sosuList = new HashSet<>();
for (int i = 1; i <= list.length; i++) {
perm(list, 0, i, sosuList);
}
System.out.println("소수 리스트입니다.");
System.out.println(sosuList);
return sosuList.size();
}
순열 구하는 로직
저는 google 에 돌아다니는 순열 코드를 참고하여 문제에 맞춰 수정을 하였습니다.
public void perm(char[] arr, int depth, int k, Set sosuList) {
if (depth == k) {
// 한번 depth 가 k로 도달하면 사이클이 돌았음. 출력함.
print(arr, k, sosuList);
return;
} else {
for (int i = depth; i < arr.length; i++) {
swap(arr, i, depth);
perm(arr, depth + 1, k, sosuList);
swap(arr, i, depth);
}
}
}
public void swap(char[] arr, int i, int j) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public void print(char[] arr, int k, Set sosuList) {
StringBuilder a = new StringBuilder();
for (int i = 0; i < k; i++) {
System.out.print(arr[i]);
a.append(arr[i]);
}
System.out.println();
isSosu(sosuList, a);
}
perm(char[] arr, int depth, int k, set sosuList)
perm( 뽑고싶은 배열, 0, 뽑고싶은 숫자, 뽑은 값을 담고싶은 배열)
depth와k가 같을 때 출력i를 증가시키면서swap()메소드로 arr[depth] 와 arr[i]의 값 대치depth를 증가시켜perm()호출1.로 이동swap()으로 대치 시킨거 복구- 끝날 때 까지 반복
제귀가 잘 이해 안되시는 분들은 테스트 케이스를 만들고 디버그 모드로 코드 한줄한줄 분석해 나가시면 이해하기 쉽습니다.
소수 구하는 로직
private void isSosu(Set sosuList, StringBuilder a) {
int b = Integer.parseInt(String.valueOf(a));
boolean sosu = true;
if (b <= 1) {
return;
}
for (int j = 2; j <= Math.sqrt(b); j++) {
if (b % j == 0) {
sosu = false;
break;
}
}
if (sosu) {
sosuList.add(b);
}
}
}
소수는 자기자신과 1로만 나눠져야 합니다.
그러니 2부터 자기지신 까지 나눠봐 나누어 떨어지는게 없으면 소수 입니다.
하지만 자기 자신 n 까지 나누지 않고 제곱근n 까지 나눠도 됩니다.
이유는
n = a * b 이고
a >= n' 이면,
a * b = n' * n' 이므로
b <= n' 가 됩니다.
예를 들어 설명을 하면 100 = 10 * 10 입니다.
a * b = 100;
a 가 5 라면
5 * 20 = 100
i가 5 일 때 소수인지 판별하는것과 i 가 20일 때 판단하는 것은 중복입니다.
따라서 100의 제곱근인 10까지 for문을 돌리면 모든 경우를 다 찾이볼 수 있습니다.
느낀 점
정말 많은 공부가 되는 문제 였습니다.
조합으로 풀 생각을 해 조합을 공부하고 아닌걸 알고 순열로 구하려고 순열 공부하고 정말 많은걸 얻어가는 문제였습니다.
특히 코드 분석하며 제귀함수에 대해 조금 더 이해 하게 된것 같습니다.
다음에 다시 한번 풀어 보면 좋을것 같습니다.
참조
java 순열 코드 https://gorakgarak.tistory.com/522