들어가며
다 풀기까지 꽤 시간이 소요된 문제. 모든 경우의 수를 구하는 상황이 처음이였고, 순열 알고리즘을 이해하고 활용하는데에 점 애를 먹어서이다.
문제
https://programmers.co.kr/learn/courses/30/lessons/42839
시도한 방법
먼저 1. 모든 경우의 수 만들기 2. 소수 찾기
로 나누어서 각 문제를 해결할 방법을 생각했다.
1은 순열 (nPr) 2는 소수의 정의를 활용했다. ( 처음엔 에라스토테네스의 체를 생각 )
중간에
- 소수판별 조건 (소수판별 대상인 수는 1또는 0이여서는 안됨)
- 중복 제거 => set 자료구조
를 놓쳐 코드를 수정했다.
근데도 전과 동일한 case들을 통과하지 못해서 하나씩 해보기로 결정.
그 과정에서 depth자리 값을 초기화 하지 않았다는 사실을 발견.
결국 DFS에서 재귀호출과정을 분석 => 초기화 코드 추가로 해결하였다. - 모든 경우의 수 DFS => 자리값 초기화
내 풀이
‚‘‘‘ import java.util.;
import java.lang.;
class Solution {
public static int count;
public int solution(String numbers) {
String[] arr = numbers.split("");
int n = arr.length;
int r = arr.length; // max
boolean[] visited = new boolean[n];
String[] output = new String[r];// String과같은 참조형 변수 초기값이 null
Arrays.fill(output,"");
Set<Integer> set = new HashSet<Integer>();
//1. 모든 경우의 수를 만든다.
perm(arr,output,visited, 0, n, r, set);
Iterator<Integer> it = set.iterator();
while (it.hasNext()) {
int num = it.next();
if(!(num==0||num==1)&& isPrime(num)){
count++;
};
}
return count;
}
static boolean isPrime(int num){
//(어떤 수 N의 양의 제곱근 이하의 수들로 N을 나눠서 한 번이라도 나누어떨어지면 합성수, 아니면 소수)
boolean result = true;
int p = (int)(Math.sqrt(num));
for(int i=2; i<=p; i++){
if(num%i==0){
result = false;
break;
}}
return result;}
static void perm(String[] arr, String[] output, boolean[] visited, int depth, int n, int r, Set<Integer> set ) { // 여기서 검증 작업
// output을 join하여 parseInt 후
if(depth!=0){
int num = Integer.parseInt(String.join("",output));
//중복되는 수 제거 (011=11) => Set 활용
set.add(num);
}
if (depth == r) {
return;
}
for (int i=0; i<n; i++) {
if (visited[i] != true) {
visited[i] = true;
output[depth] = arr[i];
perm(arr, output, visited, depth + 1, n, r, set); //perm 끝내고 여기로 돌아왔을때는 depth를 i번째 숫자(arr[i])로 설정한 모든 숫자를 완성한 상황.
//다음 i번째 숫자로 depth번째 수를 새롭게 설정할 것이므로 방금 사용한 i번째 숫자는 안쓴 것으로 설정.
visited[i] = false;
// 방금 채운 depth자리값 초기화
output[depth]="";
}
}
}
}‘‘‘
느낀점
사실 DFS 재귀(의 호출과정)를 이해하지 않은 상태에서 문제를 풀다가 막혔던 것이 가장 컸다. 그래서 하나씩 정리하다가 현 상황에서는 설정한 depth자리의 값을 초기화하는 과정이 반드시 필요함을 알게된거고.. 이것때문에 느낀게 많다.
- 역시 단편적으로 이해하고 외우면 응용을 못하게됨 ㅎ. 특정 코드 로직의 어디에 해당하는지 알아야함. 한끗차이로 문제 맞고 틀리고 엄청 갈림.
- 문제 조건도 풀면서 안까먹게 반드시 정리.
- 문제에서 예제로 준 case는 엄청난 힌트임. 각 예제가 어떤 case인지 “추상적 정의” 필요. ( 반드시 출제자는 다른 케이스의 예제를 준다. 같은 케이스의 예제는 never 없다. )
- 그리고.. 복잡한 원리 이해에는 그냥 직접 하나씩 순서대로 써가면서 이해하는게 왕도임. ( 가장 빠른 방법. 회피하면 이렇게 됨.. ) 할때 여러가지 경우 고려하면서.. 예를 들어 여기선 2개 뽑는 경우도 해보고 3개인 경우도 해봐야 코드가 모든 경우에 적용될 수 있는지 (일반화된 코드인지)를 알 수 있음 (이거때문에도 개고생. r을 2로 잡았을때는 초기화를 n==r 일때 하는 걸로 착각함. )
다른 사람 풀이
모든 경우의 수를 만들때 ‘주어진 String을 어떻게 처리했는지’가 좀 다른듯하다. 나머지 핵심적인 부분에서 사용한 개념은 동일한듯. 사실 자료형을 다루는 것이 매번 쉬운일은 아니다. 기초와 센스가 부족하면 오히려 이것을 처리하느라 시간을 보낼수도 있으니..
