코드스테이츠 Day28
<알고리즘 with Math>
- 조합은 주로 다중 반복문 이용
- 순열은 재귀함수 이용
- 중복 순열
- 순열 : boolean[]을 통해 선택한 패(true)는 중복되지 않도록 제외.
- 배열 생성시 주소값 주의
- Arrays.copyOf() : 배열 깊은 복사
- 필드 변수는 변하지 않는 경우에만 사용. 사용 지양.
<중복 순열 템플릿>
public class Solution {
public ArrayList<String[]> rockPaperScissors(int rounds) {
ArrayList<String[]> outcomes = new ArrayList<>();
return permutation(rounds, new String[]{}, outcomes);
}
public ArrayList<String[]> permutation(int roundsToGo, String[] playedSoFar, ArrayList<String[]> outcomes) {
if(roundsToGo == 0) {
outcomes.add(playedSoFar);
return outcomes;
}
String[] rps = new String[]{"rock", "paper", "scissors"};
for(int i = 0; i < rps.length; i++) {
String currentPlay = rps[i];
String[] concatArray = Arrays.copyOf(playedSoFar, playedSoFar.length + 1);
concatArray[concatArray.length - 1] = currentPlay;
outcomes = permutation(roundsToGo - 1, concatArray, outcomes);
}
return outcomes;
}
}- 결과를 담을 리스트를 선언하고, 중복 순열 함수를 결과값으로 리턴.
- 중복 순열 함수
- 매개변수 : 횟수, 리스트 요소가 될 배열, 결과 리스트
- 재귀함수의 탈출조건 : 횟수가 0이 될 때까지.
- for문을 통해 가능한 경우를 순회하면서 배열에 입력
- 재귀를 통해 리스트 요소를 횟수만큼 채우고, 모든 반복문을 실행 후 리턴.
<순열 템플릿>
public class Solution {
public ArrayList<Integer[]> newChickenRecipe(int[] stuffArr, int choiceNum) {
ArrayList<Integer> freshArr = new ArrayList<>();
for(int i = 0; i < stuffArr.length; i++) {
String str = String.valueOf(stuffArr[i]);
int[] element = str.chars().filter(c -> c == '0').toArray();
if(element.length <= 2) {
freshArr.add(stuffArr[i]);
}
}
Collections.sort(freshArr);
if (freshArr.size() == 0 || freshArr.size() < choiceNum) return null;
ArrayList<Integer[]> result = new ArrayList<>();
boolean[] visited = new boolean[freshArr.size()]; // (f,f,f)
return permutation(choiceNum, new Integer[]{}, result, freshArr, visited);
}
public ArrayList<Integer[]> permutation(int choiceNum, Integer[] bucket,
ArrayList<Integer[]> result, ArrayList<Integer> freshArr, boolean[] visited) {
if(choiceNum == 0) {
result.add(bucket);
return result;
}
for(int i = 0; i < freshArr.size(); i++) {
if(!visited[i]) {
visited[i] = true;
Integer[] concatArray = Arrays.copyOf(bucket, bucket.length + 1);
concatArray[concatArray.length - 1] = freshArr.get(i);
result = permutation(choiceNum-1, concatArray, result, freshArr, visited);
visited[i] = false;
}
}
return result;
}
}- str.chars() : 각 문자를 intstream으로 다룰 수 있게 함.
https://ryan-han.com/post/dev/java-stream/ - 결과를 담을 리스트와 중복을 피할 boolean[]을 선언하고, 순열 함수를 결과값으로 리턴.
- 순열 함수
- 매개변수 : 횟수, 리스트 요소가 될 배열, 결과 리스트, boonlean[], 순회할 리스트나 배열.
- 재귀함수의 탈출조건 : 횟수가 0이 될 때까지. (개인적으로 depth 변수를 매개변수로 추가하여 횟수를 맞추는 것보다, 횟수를 차감하여 0으로 만들어서 탈출 조건을 작성하는 게 더 깔끔한 것 같음)
- for문을 통해 가능한 경우를 순회하면서 배열에 입력
- 이미 순회한 경우는 true로 표시.
- 재귀를 통해 리스트 요소를 횟수만큼 채우고, 모든 반복문을 실행 후 리턴.
<조합 템플릿>
public class Solution {
public int boringBlackjack(int[] cards) {
// 3장을 순서와 중복 없이 고르고 더한 후, 합이 소수이면, 카운트++
int count =0;
for(int i=0; i<cards.length; i++){ // 1
for(int j=i+1; j<cards.length; j++){ // 2
for(int k=j+1; k<cards.length; k++){ // 3 4
if(isPrime(cards[i]+cards[j]+cards[k])) count++;
}
}
}
return count;
}
public boolean isPrime(int num){
for(int i=2; i<=Math.sqrt(num); i++){
if(num%i==0) return false;
}
return true;
}
}<최대 공약수 템플릿>
public class Solution {
public ArrayList<Integer[]> divideChocolateStick(int M, int N) {
int GCD = gcd(M, N);
ArrayList<Integer[]> output = new ArrayList<>();
for(int i=1; i<=GCD; i++){
if(GCD%i==0) output.add(new Integer[]{i, M/i, N/i});
}
return output;
}
public int gcd(int a, int b){
if(a%b==0) return b;
return gcd(b, a%b);
}
}- 최대 공약수 : 유클리드 호제법을 통해 재귀함수로 구함.
https://bbinya.tistory.com/45
<느낀 점>
알고리즘의 가장 큰 벽은 재귀함수가 아닐까 생각이 든다... ㅋㅋㅋ
오늘도 재귀함수의 늪에 빠져 허우적거림.
레퍼런스와 풀이 영상을 보며 이해하는 것만으로도 시간이 빠듯했다.
재귀함수 과정 하나 하나를 다 써보기도 하고 이해하기위해 갖은 노력을,,ㅋㅋ
멱집합이랑 정규표현식은 내일 공부 해야지,,
내일 순열 풀이 영상도 한 번 더 봐야겠다.
