[Coding Test] Programmers Level2 소수 찾기 (순열 조합, 소수)
Programmers Level2 소수 찾기
문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.
풀이
-
주어진
numbers
를 하나 하나 쪼갠다. -
쪼개진
number
들을 조합하여 숫자를 구성한다. 011 = 11이므로 앞이 0으로 시작하는 조합은 제외, 조합되어 중복되는 수들은 하나만 사용 -
combination
된number
들의 소수 여부를 판별하여 소수의 개수를 구한다.
코드
import java.util.Set;
import java.util.TreeSet;
class Solution {
int answer = 0;
Set<Integer> alredyExistsPrimeNumSet = new TreeSet<Integer>();
public int solution(String numbers) {
char[] numberChar = numbers.toCharArray();
int length = numberChar.length;
char[] combinationNumChar = new char[length];
boolean[] used = new boolean[length];
for(int i = 1; i <= length; i++){
recursionCombination(numberChar, used, combinationNumChar, 0, length, i);
}
return answer;
}
public void recursionCombination(char[] numberChar, boolean[] used, char[] combinationNumChar, int count, int length, int maxCombination){
if(count == maxCombination){
if(isPrimeNumber(combinationNumChar, maxCombination))
answer++;
return;
}
for(int i = 0; i < length; i++){
if(used[i])
continue;
used[i] = true;
combinationNumChar[count] = numberChar[i];
recursionCombination(numberChar, used, combinationNumChar, count + 1, length, maxCombination);
used[i] = false;
}
}
public boolean isPrimeNumber(char[] combinationNumChar, int maxCombination){
if(combinationNumChar[0] == '0')
return false;
String combinationNumStr = "";
for(int i = 0 ; i < maxCombination; i++){
combinationNumStr += combinationNumChar[i];
}
int tempNumber = Integer.parseInt(combinationNumStr);
if(tempNumber <= 1 || alredyExistsPrimeNumSet.contains(tempNumber))
return false;
for(int i = 2; i * i <= tempNumber; i++){
if(tempNumber % i == 0)
return false;
}
alredyExistsPrimeNumSet.add(tempNumber);
return true;
}
}
코드 풀이
- 주어진
String
numbers
를String
의toCharArray()
method를 이용해char[]
로 바꾼다.char[] numberChar
생성 -
numbers
의 length를 구한다. -
쪼개진 숫자 문자를 조합할때 사용할
char
combincationNumChar[]
배열을 생성한다. -
조합할때 해당 숫자를 사용했는지 여부를 가릴
boolean
used[]
배열을 생성한다. -
중복되는 소수 카운팅을 제외하기 위해
Set<Integer>
alredyExistsPrimeNumSet
을 생성한다. 데이터 생성에는 HashSet보다 느리지만, 잦은 검색에는 TreeSet이 더 효율적이므로 TreeSet 사용 -
재귀를 이용하여 숫자들을 조합할
void
recursionCombination
method를 생성, parameter로는 아래 변수들을 사용한다. 6.1 조합할 숫자 문자의 배열char[] numberChar
6.2 조합에서 해당 숫자를 사용했는지 판단용도boolean[] used
6.3 조합된 숫자 문자조합이 각각 담길char[] combinationNumChar
6.4 해당 문자열의 최대 길이int length
6.5 해당 조합에서 최대로 가능한 자리수를 나타내는int maxCombination
6.6 해당 조합에서 현재 조합중인 자리수를 나타내는int count
-
소수 여부를 판별할
boolean
isPrimeNumber
method를 생성, parameter로는 아래 변수들을 사용한다. 7.1 조합된 숫자의 문자가 담긴char[] combinationNumChar
7.2 해당 조합에서 최대로 가능한 자리수를 나타내는int maxCombination
-
solution
에서recursionCombination
method를 1부터 조합될 수 있는 문자열의 개수(length
)만큼 반복한다. 1부터 시작하는 이유는 1자리 수 부터 시작하기 위함 8.1maxCombination
에i
를 넣음으로써 1자리 부터 주어진numbers
의 길이 만큼의 자리수 까지 숫자들을 조합하여 소수 여부를 판별한다. 8.2 해당 조합에서 현재 조합중인 자리수를 나타내는int count
부분에 0을 넣는다. 8.3recursionCombination
에서는count
를 1개씩 늘려서 최대maxCombination
이 도달하면 지금까지 조합에 사용하기 위해 저장했던combinationNumChar
를isPrimeNumber
에maxCombination
와 함께 parameter로 사용한다. -
isPrimeNumber
에서 조합될 숫자를 조합하여 숫자로 변환 후 소수 여부를 판별한다. 9.1 조합될 첫 숫자가0
인 경우false
를 return한다. 9.2combinationNumChar[]
안에 숫자들을 for문으로String
combinationNumStr
에 붙여준다. 9.2combinationNumStr
을int
tempNumber
로 바꾼다. 9.3tempNumber
가 1이거나 이미answer
에서 카운팅된 소수들이 저장된alredyExistsPrimeNumSet
에 포함되면false
를 return한다. 9.4tempNumber
를 2부터tempNumber
의 제곱근까지%
연산 해보고 나누어 떨이지면false
를 return한다. 9.5 마지막 과정까지 나누어 떨어지지 않고 실행되었다면alredyExistsPrimeNumSet
에tempNumber
를 add한 후true
를 return한다. solution
에서 조합될 수 있는 문자열의 개수(length
)만큼 반복 하던recursionCombination
method가 종료된다.answer
에는recursionCombination
method에서 각 자리수의 최대 조합 가능 개수에서isPrimeNumber
method를 통해 true일 경우answer
의 값이 증가 하였으므로answer
를 return하여 답을 구한다.
댓글남기기