반응형
자바 문법 정도만 레퍼런스를 받고, 알고리즘 자체는 직접 구현한 풀이 방법이다.
set을 활용한 부분에 있어서는 다른 사람들의 코드를 살펴보니 대부분 사용하는 편인 것 같았다.
전체적인 진행 방향은 다음과 같다.
- 문자열에 들어 있는 0~9 숫자들을 INT 타입으로 바꾸어 int배열에 저장한다.
- 배열에 저장된 수를 가지고, 직접 짠 조합 알고리즘을 통해 가능한 모든 숫자 조합을 찾아 SET 자료구조에 저장한다.
- SET에 저장된 숫자가 소수인지 판별하여, 소수인 경우에만 카운트를 한다.
SET 자료구조
- 중복된 값을 저장하지 않아서 유니크한 값으로만 구성된다.
- Set 자료구조는 인터페이스라서 HashSet로 Integer를 명시해서 생성해야 한다.
- 문자열에 들어있는 숫자를 조합해 나올 수 있는 모든 수를 구해야 한다.
- permutation 함수를 이용할 수 있었는데, 존재를 까먹고 조합 알고리즘을 직접 구현함.
- 문자열의 각 숫자를 INT 형식으로 바꾸어 INT타입의 배열에 저장해줌.
- 그 INT배열을 가지고 숫자를 조합하는데, 중복된 숫자 값이 생성될 수 있으므로 Set 자료구조를 사용해서 중복된 값이 들어가지 않도록 하였음.
- 일단, 자리수 하나의 숫자들을 set에 저장.
- 그리고 각각의 저장된 숫자를 제외한 배열 값을 갖는 새로운 배열을 만들어서 재귀적으로 가능한 조합을 만들 수 있도록 하는 함수의 인자로 넣어줌.
- 그 함수가 makePrime인데, 함수이름만 makePrime이고, 사실상 조합을 만드는 함수임. 나의 실수.
- makePrime함수에서는 주어진 배열과, set, 이전에 이미 방문?했던 앞자리 수를 인자로 받음.
- 그리고 앞자리수가 하나 제외되어있는 주어진 배열에 있는 값을 하나씩 앞자리 수에 더하여 수를 만들고 set에 집어 넣음.
- 이때 앞자리 수에 10을 곱하고 배열에 있는 값 중 현재 가리키는 값을 더함으로써 새로운 수를 만들 수 있음.
- 그리고 makePrime함수를 재귀호출함으로써 위의 과정을 반복하다 보면, set에는 모든 가능한 숫자 조합이 만들어져 있음.
- 이 set을 가지고, 순회하면서, 만약 값이 0,1이라면 소수로 포함하지 않고, 2,3,5,7이라면 소수로 카운팅 함.
- 그리고 2의 배수라면 소수로 포함하지 않고, 2의 배수가 아니라면 해당 값을 3부터 (해당값/3)을 한 값까지로 나누었을 때 나머지가 0이면 => 1과 자기 자신 말고도 나눠지는 값이 있다는 것이므로 소수가 아니고, 카운팅 하지 않는다. 만약 그런 값이 하나도 없었다면(=>불리언 값으로 판단함) 소수로 카운팅한다.
- 위의 과정을 거침으로써 소수의 개수를 찾을 수 있다.
- 다소 복잡하게 보이지만, 스스로 짰다는 것에 의의를 둔다.
- 메소드를 익히는 것도 중요해 보인다.
전체 코드이다.
import java.util.HashSet;
import java.util.Set;
class Solution {
public int[] removeValue(int[] arr, int remove){
int[] newarr = new int[arr.length-1];
int first = 0;
int index = 0;
for(int i : arr){
if(i==remove && first==0){
first = 1;
}else{
newarr[index]=i;
index++;
}
}
return newarr;
}
public void makePrime(int[] arr, Set<Integer> set, int prev){
for(int i=0; i<arr.length; i++){
set.add(prev*10+arr[i]);
int[] newarr = removeValue(arr, arr[i]);
makePrime(newarr, set, prev*10+arr[i]);
}
}
public int solution(String numbers) {
int answer = 0;//count
int[] nums = new int[numbers.length()];
Set<Integer> set = new HashSet<>();
for(int i=0; i<numbers.length(); i++){
nums[i] = Character.getNumericValue(numbers.charAt(i));
}
for(int i=0; i<nums.length; i++){
set.add(nums[i]);
int[] newarr = removeValue(nums, nums[i]);
makePrime(newarr, set, nums[i]);
}
//set에는 가능한 모든 값들이 생성된다.
for(int i : set){
if(i==0 || i==1){//0이거나 1이면 패스
continue;
}
if(i==2 || i==3 || i==5 || i==7){//2,3,5,7이면 count
answer++;
continue;
}
if(i%2==0){//2의 배수이므로 패스
continue;
}else{
int isPrime = 1;
for(int j=3; j<=(i/3); j++){
if(i%j==0){
isPrime=0;
break;
}
}
if(isPrime==1) answer++;
}
}
return answer;
}
}
이 문제를 푸는데만 1시간 반이 걸렸지만, 성공한게 뿌듯했다.
반응형
'CO-TE > 프로그래머스' 카테고리의 다른 글
[프로그래머스] JAVA LV3 "단어 변환" 풀이 / DFS 사용 (0) | 2023.10.24 |
---|---|
[프로그래머스] JAVA LV2 "더 맵게" 풀이방법 / 우선순위 큐 - min heap 사용 (0) | 2023.10.20 |
[프로그래머스] JAVA LV2 "올바른 괄호" 풀이방법 / 스택 사용 (1) | 2023.10.19 |
[프로그래머스] JAVA LV2 "가장 큰 수" 풀이 방법 / Arrays.sort / 람다식 사용 (1) | 2023.10.19 |
[프로그래머스] MYSQL LV3 조건에 맞는 사용자와 총 거래금액 조회하기 / GROUP BY 이용 (0) | 2023.10.19 |