순열, 조합

✏️ 순열 (Permutation)

• n개 중에 m개를 선택해 순서에 상관 있게 뽑는 경우의 수

import java.util.*;

public class Solution { 
	public ArrayList<Integer[]> newChickenRecipe(int[] stuffArr, int choiceNum) {
    // TODO:
    ArrayList<Integer> fresh = new ArrayList<>();
    for (int i = 0; i < stuffArr.length; i++){
      char[] arr = (Integer.toString(stuffArr[i])).toCharArray();
      int count = 0;
      boolean check = true;
      for (int j = 0; j < arr.length; j++){
        if(arr[j]=='0'){
          count+=1;
        }
        if (count == 3){
          check = false;
          break;
        }
      }
      if (check == true){
        fresh.add(stuffArr[i]);
      }
    }
    Collections.sort(fresh);
    if (fresh.size()==0 || fresh.size()<choiceNum){
      return null;
    }
    
    ArrayList<Integer[]> res = new ArrayList<>();
    boolean[] visited = new boolean[fresh.size()];

    return per(choiceNum, new Integer[choiceNum], fresh, visited, res, 0);
  }
  public ArrayList<Integer[]> per(int choiceNum, Integer[] temp, ArrayList<Integer> fresh, boolean[] visited, ArrayList<Integer[]> res, int current){
    if (current == choiceNum){
      Integer[] arr = Arrays.copyOf(temp, temp.length);
      res.add(arr);
      return res;
    }
    for (int i = 0; i < fresh.size(); i++){
      if(!visited[i]){
        visited[i] = true;
        temp[current] = fresh.get(i);
        res = per(choiceNum, temp, fresh, visited, res, current+1);
        visited[i] = false;
      }
    }
    return res;
  }
}

✏️ 중복 순열

import java.util.*;

public class Solution { 
	public ArrayList<String[]> rockPaperScissors(int rounds) {
    // TODO:
    ArrayList<String[]> res = new ArrayList<>();
    String[] temp = new String[rounds];
    return per(rounds, new String[rounds], 0, res);
	}
  public ArrayList<String[]> per(int pick, String[] temp, int current, ArrayList<String[]> res){ 
    String[] type = new String[]{"rock","paper","scissors"};
    if (pick == current){
      String[] arr = Arrays.copyOf(temp, temp.length);
      res.add(arr);
      return res;
    }
    for (int i = 0; i < type.length; i++){
      temp[current] = type[i]; 
      res = per(pick, temp, current+1, res);
    }
    return res;
  }
}

✏️ 조합 (Combination)

• 순서에 관계 없이 n개 중 m개를 뽑는 경우의 수

import java.util.*;

public class Solution { 
	public int boringBlackjack(int[] cards) {
    // TODO:
    // 1. 카드 경우의 수 구하기
    ArrayList<Integer> comb = new ArrayList<>();
    for (int i = 0; i < cards.length; i++){
      for (int j = i+1; j < cards. length; j++){
        for (int k = j+1; k < cards.length; k++){
          comb.add(cards[i]+cards[j]+cards[k]);
        }
      }
    }
    // 2. 소수 찾기
    int count = 0;
    for (int i = 0; i < comb.size(); i++){
      if(comb.get(i)%2 == 0){
        continue;
      }
      int check = 0;
      double l = Math.sqrt(comb.get(i));
      for (int j = 3; j <= l; j++){
        if (comb.get(i)%j == 0){
          check += 1;
          break;
        }
      }
      if (check == 0){
        count += 1;
      }
    }
    return count;
	} 
}

✏️ 중복 조합

✏️ 멱집합

import java.util.*;

public class Solution { 
	public ArrayList<String[]> missHouseMeal(String[] sideDishes) {
    // TODO:
    ArrayList<String[]> res = new ArrayList<>();
    Stack<String> temp = new Stack<>();
    Arrays.sort(sideDishes);
    res = search(temp, 0, sideDishes, res);
    res.sort((o1,o2) -> {
      return Arrays.toString(o1).compareTo(Arrays.toString(o2));
    });
    return res;
  }
  public ArrayList<String[]> search(Stack<String> temp, int idx, String[] sideDishes, ArrayList<String[]> res){
    if (idx == sideDishes.length){
      String[] arr = temp.toArray(new String[0]);
      res.add(arr);
      return res;
    }
    else{
      //sideDishes[idx]를 부분집합에 포함하는 경우
      temp.add(sideDishes[idx]);
      search(temp,idx+1, sideDishes, res);
      
      //포함하지 않는 경우
      temp.pop();
      search(temp, idx+1, sideDishes, res);
    }
    return res;
  }
}