DailyCoding
Q: 띄어쓰기2개 1개로 바꿔라
A: 아래 3가지 방법으로 가능할 것 같다.
-
replaceAll()메서드를 사용하여 공백 2개를 1개로 바꾸는 방법
-
split()메서드를 이용해 공백2개를 기준으로 끊어서 문자열을 나누고join()을 이용해 공백1개와 끊은 문자열들을 합치는 방법
-
- 반복문 사용해서 공백 연속으로 나올 때를 이용
import java.util.Arrays;
public class DoubleSpaceToSingle {
public String convertDoubleSpaceToSingle(String str) {
str = str.replaceAll(" ", " "); // 공백 2개를 1개로 바꾸기
return str;
}
public String convertDoubleSpaceToSingle2(String str) {
String[] words = str.split(" ");
System.out.println(Arrays.toString(words));
return String.join(" ", words);
}
public String convertDoubleSpaceToSingle3(String str) {
String result = "";
char before = 0;
for(int i = 0; i < str.length(); i++) {
if(str.charAt(i) != ' ' || before != ' ') {
result += str.charAt(i);
}
before = str.charAt(i);
}
return result;
}
}
//입력
"Double space with Double "
//출력
Double space with Double
[Double, space with, Double]
Double space with Double
Double space with Double
Algorithm with Math (순열 / 조합)
순열(permutation)과 조합(Combination)
-
GCD/LCM = 최대공약수/ 최소공배수
-
순열 : 요소 n개 중에 m개를 선택하여 순서에 상관 있게 뽑는 경우의 수.
- nPm = n!/(n-m)! -
조합 : 순서에 상관없이 요소 n개 중에 m개를 뽑는 경우의 수.
- nCm = n!/((n-m)!*m!)
순열과 조합은 주로 재귀로 푼다.
Quiz
5. 가위바위보 경우의 수
가위바위보를 하는 횟수에 대한 입력을 받으면 내가 낼 수 있는 모든 경우의 수를 출력하라.
import java.util.ArrayList;
import java.util.Arrays;
public class RockPaperScissors {
String[] rps = {"rock","paper","scissors"}; // class변수 최대한 피하자.
public ArrayList<String[]> rockPaperScissors(int rounds) {
return ref(0,rounds,new String[0],new ArrayList<String[]>());
}
public ArrayList<String[]> ref(int count, int rounds, String[] strarr, ArrayList<String[]> list){
if(rounds == count){
list.add(strarr);
return list;
}
strarr = Arrays.copyOf(strarr, strarr.length+1); // 배열 자리 늘리기
for(int i=0; i < rps.length; i++){
strarr[strarr.length-1] = rps[i]; // 마지막 인덱스에 값 추가
//System.out.println(Arrays.deepToString(list.toArray()));
list = ref(count+1,rounds,strarr,list);
}
return list;
}
}
//입력
rounds = 3
//출력
[rock, rock, scissors]
[rock, rock, scissors]
[rock, rock, scissors]
[rock, paper, scissors]
[rock, paper, scissors]
[rock, paper, scissors]
[rock, scissors, scissors]
[rock, scissors, scissors]
[rock, scissors, scissors]
[paper, rock, scissors]
[paper, rock, scissors]
[paper, rock, scissors]
[paper, paper, scissors]
[paper, paper, scissors]
[paper, paper, scissors]
[paper, scissors, scissors]
[paper, scissors, scissors]
[paper, scissors, scissors]
[scissors, rock, scissors]
[scissors, rock, scissors]
[scissors, rock, scissors]
[scissors, paper, scissors]
[scissors, paper, scissors]
[scissors, paper, scissors]
[scissors, scissors, scissors]
[scissors, scissors, scissors]
[scissors, scissors, scissors]멘마지막값만 전부 scissors로 덮인다...
배열을 생성하고 값을 바꾸고 list에 넣어주는 과정에서 배열이 계속 같은 변수명을 사용해 잘못덮어씌어지는 문제가 발생한 것이었다.
아래 2가지 방법으로 고칠 수 있었다.
(둘 중 하나만 해도 됨.)
- 배열에 값 추가하기 직전에 배열 길이 늘려주기
package Algorithm;
import java.util.ArrayList;
import java.util.Arrays;
public class RockPaperScissors {
String[] rps = {"rock","paper","scissors"};
public ArrayList<String[]> rockPaperScissors(int rounds) {
return ref(0,rounds,new String[0],new ArrayList<String[]>());
}
public ArrayList<String[]> ref(int count, int rounds, String[] strarr, ArrayList<String[]> list){
if(rounds == count){
list.add(strarr); //.clone 사용하자.. 깊은복사
return list;
}
//////////////////////////////수정된 부분//////////////////////////////
//strarr = Arrays.copyOf(strarr, strarr.length+1); // 배열 자리 늘리기, 최대한 add하는 부분에 추가하는게 좋음
for(int i=0; i < rps.length; i++){
String[] strarr2 = Arrays.copyOf(strarr, strarr.length+1); // 배열 자리 늘리기, 최대한 add하는 부분에 추가하는게 좋음
strarr2[strarr2.length-1] = rps[i]; // 마지막 인덱스에 값 추가
list = ref(count+1,rounds,strarr2,list);
//System.out.println(Arrays.deepToString(list.get(0)));
}
//////////////////////////////수정된 부분//////////////////////////////
return list;
}
}
- 깊은복사 이용하기
package Algorithm;
import java.util.ArrayList;
import java.util.Arrays;
public class RockPaperScissors {
String[] rps = {"rock","paper","scissors"};
public ArrayList<String[]> rockPaperScissors(int rounds) {
return ref(0,rounds,new String[0],new ArrayList<String[]>());
}
public ArrayList<String[]> ref(int count, int rounds, String[] strarr, ArrayList<String[]> list){
if(rounds == count){
//////////////////////////////수정된 부분//////////////////////////////
list.add(strarr.clone); //.clone 사용하자.. 깊은복사
//////////////////////////////수정된 부분//////////////////////////////
return list;
}
strarr = Arrays.copyOf(strarr, strarr.length+1); // 배열 자리 늘리기, 최대한 add하는 부분에 추가하는게 좋음
for(int i=0; i < rps.length; i++){
strarr = Arrays.copyOf(strarr, strarr.length+1); // 배열 자리 늘리기, 최대한 add하는 부분에 추가하는게 좋음
strarr[strarr.length-1] = rps[i]; // 마지막 인덱스에 값 추가
list = ref(count+1,rounds,strarr,list);
//System.out.println(Arrays.deepToString(list.get(0)));
}
return list;
}
}
나중에 사용할 부분을 미리 바꾸는 방식은 예상치 못한 영향을 줄 수 있다. 최대한 사용하기 직전에 만들자.
변수선언 한줄 아낀다고 큰차이가 생기지 않는다. 안정성을 더 우선시하며 코드를 짜자.
6. 순열 조합
1과0으로 이루어진 int형 요소들을 배열로 입력받아 조합 가능한 경우의 수를 모두 출력하시오.
- 입력받는 배열의 요소값은 항상 1로 시작
- 같은 요소 중복사용 금지
- 요소값에 000이 포함되어있으면 사용하지 말아라
- 조합 및 요소는 오름차순으로 정렬하라.
package Algorithm;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.IntStream;
public class Permutation {
public ArrayList<Integer[]> newChickenRecipe(int[] stuffArr, int choiceNum) {
for(int i=0; i<stuffArr.length; i++){
if(IntStream.of(stuffArr[i]).anyMatch(x -> x == 000)){ // 0이 연속3개 있으면 i번째 요소 삭제
int[] arr1 = Arrays.copyOfRange(stuffArr, 0, i);
int[] arr2 = Arrays.copyOfRange(stuffArr,i+1, stuffArr.length);
stuffArr = new int[stuffArr.length-1];
System.arraycopy(arr1,0,stuffArr,0,arr1.length);
System.arraycopy(arr2,0,stuffArr,arr1.length,arr2.length);
}
}
if(stuffArr.length==0||stuffArr.length<choiceNum) return null;
//Integer[] stuffArr2 = Arrays.stream(stuffArr.clone()).boxed().toArray(Integer[]::new); // int형 배열 -> Integer형 배열
return makeList(stuffArr, choiceNum, new ArrayList<Integer[]>(), 0, new int[0]);
}
public ArrayList<Integer[]> makeList(int[] stuffArr, int choiceNum, ArrayList<Integer[]> list, int count, int[] arr){
if(count==choiceNum) {
Integer[] arr3 = Arrays.stream(arr.clone()).boxed().toArray(Integer[]::new); // int형 배열 -> Integer형 배열
list.add(arr3);
return list;
}
for(int i=0; i<stuffArr.length; i++){
int[] arr2 = Arrays.copyOf(arr, arr.length+1);
arr2[arr2.length-1] = stuffArr[i];
makeList(stuffArr,choiceNum,list,count+1,arr2);
}
return list;
}
}
//입력
permutation.newChickenRecipe(new int[]{1,10,1100,1111},2)
//출력
[1, 1]
[1, 10]
[1, 1100]
[1, 1111]
[10, 1]
[10, 10]
[10, 1100]
[10, 1111]
[1100, 1]
[1100, 10]
[1100, 1100]
[1100, 1111]
[1111, 1]
[1111, 10]
[1111, 1100]
[1111, 1111]
종료 코드 0(으)로 완료된 프로세스
중복사용 금지 조건을 빼먹었다.
package Algorithm;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.IntStream;
public class Permutation {
public ArrayList<Integer[]> newChickenRecipe(int[] stuffArr, int choiceNum) {
for(int i=0; i<stuffArr.length; i++){
if(IntStream.of(stuffArr[i]).anyMatch(x -> x == 000)){ // 0이 연속3개 있으면 i번째 요소 삭제
int[] arr1 = Arrays.copyOfRange(stuffArr, 0, i);
int[] arr2 = Arrays.copyOfRange(stuffArr,i+1, stuffArr.length);
int[] stuffArr = new int[stuffArr.length-1];
System.arraycopy(arr1,0,stuffArr,0,arr1.length);
System.arraycopy(arr2,0,stuffArr,arr1.length,arr2.length);
}
}
if(stuffArr.length==0||stuffArr.length<choiceNum) return null;
return makeList(stuffArr, choiceNum, new ArrayList<Integer[]>(), 0, new int[0]);
}
public ArrayList<Integer[]> makeList(int[] stuffArr, int choiceNum, ArrayList<Integer[]> list, int count, int[] arr){
if(count==choiceNum) {
Integer[] arr3 = Arrays.stream(arr.clone()).boxed().toArray(Integer[]::new); // int형 배열 -> Integer형 배열
list.add(arr3);
return list;
}
for(int i=0; i<stuffArr.length; i++){
boolean containValue = true;
for(int o : arr){
if(o==stuffArr[i]) containValue = false;
}
if(containValue) {
int[] arr2 = Arrays.copyOf(arr, arr.length + 1);
arr2[arr2.length - 1] = stuffArr[i];
makeList(stuffArr, choiceNum, list, count + 1, arr2);
}
}
return list;
}
}
//입력
permutation.newChickenRecipe(new int[]{11, 1, 10, 1111111111, 10000}, 4);
//출력
[11, 1, 10, 1111111111]
[11, 1, 10, 10000]
[11, 1, 1111111111, 10]
[11, 1, 1111111111, 10000]
[11, 1, 10000, 10]
[11, 1, 10000, 1111111111]
[11, 10, 1, 1111111111]
[11, 10, 1, 10000]
[11, 10, 1111111111, 1]
[11, 10, 1111111111, 10000]
[11, 10, 10000, 1]
이하 생략000이 포함 된 요소 제거가 제대로 안되고 있다.
위에 작성한 조건식 if(IntStream.of(stuffArr[i]).anyMatch(x -> x == 000))이 부분은 000이라는 값의 요소가 있냐고 묻는 것.
요소값이 000인지 알아보는 것은 다른 문제다.
package Algorithm;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.IntStream;
public class Permutation {
public ArrayList<Integer[]> newChickenRecipe(int[] stuffArr, int choiceNum) {
String[] strStuff = new String[stuffArr.length];
for(int i=0; i<stuffArr.length; i++) {
strStuff[i] = String.valueOf(stuffArr[i]);
}
System.out.println("stuff = "+ Arrays.toString(strStuff));
for(int i=0; i<stuffArr.length; i++){
if(strStuff[i].contains("000")){ // 0이 연속3개 있으면 i번째 요소 삭제
int[] arr1 = Arrays.copyOfRange(stuffArr, 0, i);
int[] arr2 = Arrays.copyOfRange(stuffArr,i+1, stuffArr.length);
stuffArr = new int[stuffArr.length-1];
System.arraycopy(arr1,0,stuffArr,0,arr1.length);
System.arraycopy(arr2,0,stuffArr,arr1.length,arr2.length);
}
}
if(stuffArr.length==0||stuffArr.length<choiceNum) return null;
return makeList(stuffArr, choiceNum, new ArrayList<Integer[]>(), 0, new int[0]);
}
public ArrayList<Integer[]> makeList(int[] stuffArr, int choiceNum, ArrayList<Integer[]> list, int count, int[] arr){
if(count==choiceNum) {
Integer[] arr3 = Arrays.stream(arr.clone()).boxed().toArray(Integer[]::new); // int형 배열 -> Integer형 배열
list.add(arr3);
return list;
}
for(int i=0; i<stuffArr.length; i++){
boolean containValue = true;
for(int o : arr){
if(o==stuffArr[i]) containValue = false;
}
if(containValue) {
int[] arr2 = Arrays.copyOf(arr, arr.length + 1);
arr2[arr2.length - 1] = stuffArr[i];
makeList(stuffArr, choiceNum, list, count + 1, arr2);
}
}
return list;
}
}
//출력
[11, 1, 10, 1111111111]
[11, 1, 1111111111, 10]
[11, 10, 1, 1111111111]
[11, 10, 1111111111, 1]
[11, 1111111111, 1, 10]
[11, 1111111111, 10, 1]
[1, 11, 10, 1111111111]
[1, 11, 1111111111, 10]
[1, 10, 11, 1111111111]
[1, 10, 1111111111, 11]
[1, 1111111111, 11, 10]
[1, 1111111111, 10, 11]
[10, 11, 1, 1111111111]
[10, 11, 1111111111, 1]
[10, 1, 11, 1111111111]
[10, 1, 1111111111, 11]
[10, 1111111111, 11, 1]
[10, 1111111111, 1, 11]
[1111111111, 11, 1, 10]
[1111111111, 11, 10, 1]
[1111111111, 1, 11, 10]
[1111111111, 1, 10, 11]
[1111111111, 10, 11, 1]
[1111111111, 10, 1, 11]
이제 오름차순으로 정렬만 해주면 된다.
package Algorithm;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.IntStream;
public class Permutation {
public ArrayList<Integer[]> newChickenRecipe(int[] stuffArr, int choiceNum) {
String[] strStuff = new String[stuffArr.length];
int[] stuffArr2 = new int[stuffArr.length];
for(int i=0; i<stuffArr.length; i++) {
strStuff[i] = String.valueOf(stuffArr[i]);
}
for(int i=0; i<stuffArr.length; i++){
if(strStuff[i].contains("000")){ // 0이 연속3개 있으면 i번째 요소 삭제
int[] arr1 = Arrays.copyOfRange(stuffArr, 0, i);
int[] arr2 = Arrays.copyOfRange(stuffArr,i+1, stuffArr.length);
stuffArr2 = new int[stuffArr.length-1];
System.arraycopy(arr1,0,stuffArr2,0,arr1.length);
System.arraycopy(arr2,0,stuffArr2,arr1.length,arr2.length);
}
}
Arrays.sort(stuffArr2); // 오름차순으로 정렬
if(stuffArr2.length==0||stuffArr2.length<choiceNum) return null;
return makeList(stuffArr2, choiceNum, new ArrayList<Integer[]>(), 0, new int[0]);
}
public ArrayList<Integer[]> makeList(int[] stuffArr, int choiceNum, ArrayList<Integer[]> list, int count, int[] arr){
if(count==choiceNum) {
Integer[] arr3 = Arrays.stream(arr.clone()).boxed().toArray(Integer[]::new); // int형 배열 -> Integer형 배열
list.add(arr3);
return list;
}
for(int i=0; i<stuffArr.length; i++){
boolean containValue = true;
for(int o : arr){
if(o==stuffArr[i]) containValue = false;
}
if(containValue) {
int[] arr2 = Arrays.copyOf(arr, arr.length + 1);
arr2[arr2.length - 1] = stuffArr[i];
makeList(stuffArr, choiceNum, list, count + 1, arr2);
}
}
return list;
}
}
//출력
[1, 10, 11, 1111111111]
[1, 10, 1111111111, 11]
[1, 11, 10, 1111111111]
[1, 11, 1111111111, 10]
[1, 1111111111, 10, 11]
[1, 1111111111, 11, 10]
[10, 1, 11, 1111111111]
[10, 1, 1111111111, 11]
[10, 11, 1, 1111111111]
[10, 11, 1111111111, 1]
[10, 1111111111, 1, 11]
[10, 1111111111, 11, 1]
[11, 1, 10, 1111111111]
[11, 1, 1111111111, 10]
[11, 10, 1, 1111111111]
[11, 10, 1111111111, 1]
[11, 1111111111, 1, 10]
[11, 1111111111, 10, 1]
[1111111111, 1, 10, 11]
[1111111111, 1, 11, 10]
[1111111111, 10, 1, 11]
[1111111111, 10, 11, 1]
[1111111111, 11, 1, 10]
[1111111111, 11, 10, 1]
오름차순 정렬은 됐지만 위 코드의 경우 if(strStuff[i].contains("000"))이 조건식이 true가 아닐 경우 stuffArr2가 0으로 채워진 배열이 돼서 제대로 기능하지 않는다.
package Algorithm;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.IntStream;
public class Permutation {
public ArrayList<Integer[]> newChickenRecipe(int[] stuffArr, int choiceNum) {
String[] strStuff = new String[stuffArr.length];
int[] stuffArr2 = new int[stuffArr.length];
for(int i=0; i<stuffArr.length; i++) {
strStuff[i] = String.valueOf(stuffArr[i]);
}
for(int i=0; i<stuffArr.length; i++){
if(strStuff[i].contains("000")){ // 0이 연속3개 있으면 i번째 요소 삭제
int[] arr1 = Arrays.copyOfRange(stuffArr, 0, i);
int[] arr2 = Arrays.copyOfRange(stuffArr,i+1, stuffArr.length);
stuffArr2 = new int[stuffArr.length-1];
System.arraycopy(arr1,0,stuffArr2,0,arr1.length);
System.arraycopy(arr2,0,stuffArr2,arr1.length,arr2.length);
}
}
//////////////////////////////////수정된 부분//////////////////////////////////
if(stuffArr2.length==stuffArr.length) stuffArr2 = stuffArr.clone();
//////////////////////////////////수정된 부분//////////////////////////////////
Arrays.sort(stuffArr2); // 오름차순 정렬
if(stuffArr2.length==0||stuffArr2.length<choiceNum) return null;
return makeList(stuffArr2, choiceNum, new ArrayList<Integer[]>(), 0, new int[0]);
}
public ArrayList<Integer[]> makeList(int[] stuffArr, int choiceNum, ArrayList<Integer[]> list, int count, int[] arr){
if(count==choiceNum) {
Integer[] arr3 = Arrays.stream(arr.clone()).boxed().toArray(Integer[]::new); // int형 배열 -> Integer형 배열
list.add(arr3);
return list;
}
for(int i=0; i<stuffArr.length; i++){
boolean containValue = true;
for(int o : arr){
if(o==stuffArr[i]) containValue = false;
}
if(containValue) {
int[] arr2 = Arrays.copyOf(arr, arr.length + 1);
arr2[arr2.length - 1] = stuffArr[i];
makeList(stuffArr, choiceNum, list, count + 1, arr2);
}
}
return list;
}
}
모든 테스트케이스 통과.
7. 뽑은카드 합 소수 판단
입력받는 카드들 중 3개를 뽑았을 때 카드의 합이 소수인 경우의 수를 구하시오.
import java.util.*;
public class SumIsPrimeNumber {
public int boringBlackjack(int[] cards) {
ArrayList<Integer> result = 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++) {
int sum = cards[i]+cards[j]+cards[k];
if(!result.contains(sum)) result.add(sum);
}
}
}
System.out.println(result.toString());
int count=0;
for(int o:result){
boolean bo = true;
for (int i = 3; i < o / 2; i = i + 2) {
if(o%2==0) {
bo = false;
break;
}else if(o%i==0){
bo = false;
break;
}
}
if(bo) count++;
}
return count;
}
}
//입력
sumIsPrimeNumber.boringBlackjack(new int[]{1,2,3,4})
//출력
[6, 7, 8, 9]
6
7
count = 26이 2,3의 배수인데 false처리가 안되고 소수로 판별되었다.
package Algorithm;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
public class SumIsPrimeNumber { // 입력받는 카드 중 3개 뽑아서 합이 소수인 경우의 수 구하기
public int boringBlackjack(int[] cards) {
ArrayList<Integer> result = new ArrayList<>();
for(int i = 0; i < cards.length; i++) { // 3개 뽑은 합 나열하기
for(int j = i + 1; j < cards.length; j++) {
for(int k = j + 1; k < cards.length; k++) {
int sum = cards[i]+cards[j]+cards[k];
//if(!result.contains(sum)) result.add(sum); // sum값 중복 방지하고 싶으면 이거 사용
result.add(sum);
}
}
}
System.out.println(result.toString());
int count=0;
for(int o:result){ // 소수판별
boolean bo = true;
//////////////////////////////수정된 부분//////////////////////////////
if(o%2==0) bo = false;
for (int i = 3; i <=(int) Math.sqrt(o); i+=2) {
if(o%i==0){
bo = false;
break;
}
}
//////////////////////////////수정된 부분//////////////////////////////
if(bo) {
count++;
System.out.println(o);
}
}
return count;
}
}
짝수일 경우를 for문 밖으로 빼주니 정상작동한다.
처음에 문제가 중복된 sum값을 제외해야하는 줄 알고 if문을 이용해 중복된 값을 더하지 않았었다.
if문 외에도 아래와 같이 collector를 이용해서 중복을 막을 수 있다.
collector 사용방법
package Algorithm;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
public class SumIsPrimeNumber {
public int boringBlackjack(int[] cards) {
ArrayList<Integer> result = 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++) {
int sum = cards[i]+cards[j]+cards[k];
//if(!result.contains(sum)) result.add(sum);
result.add(sum);
}
}
}
List<Integer> collect = result.stream().distinct().collect(Collectors.toList());
System.out.println(result.toString());
int count=0;
for(int o:collect){
boolean bo = true;
if(o%2==0) bo = false;
for (int i = 3; i <=(int) Math.sqrt(o); i+=2) {
if(o%i==0){
bo = false;
break;
}
}
if(bo) {
count++;
System.out.println(o);
}
}
return count;
}
}8. 유클리드 호제법
유클리드 호제법을 이용해 입력받는 M과 N을 골고루 나눠줄 수 있는 경우의 수를 구하시오.
- 남는 M,N없이 나눠줘야 함.
public ArrayList<Integer[]> divideChocolateStick(int M, int N) {
ArrayList<Integer[]> result = new ArrayList<>();
int GCD = euc(M,N); // 최대공약수
for(int i=1; i<=GCD; i++) { // i = 인원수
if(M%i==0&&N%i==0){
Integer[] ad = {i,M/i,N/i};
result.add(ad);
}
}
return result;
}
public int euc(int M, int N) {
// 큰숫자를 작은숫자로 나눈 나머지를 계산
int rest = M % N;
// 나머지가 0이면 작은숫자가 최대공약수이므로 작은숫자 리턴
if (rest == 0) {
return N;
} else if(M>N){
return euc(N, rest);
} else if(M<=N){
return euc(M,rest);
}
return 1;
//입력
M=4,N=8
//출력
[1, 4, 8]
[2, 2, 4]
[4, 1, 2]모든 테스트케이스 통과.
더 간단하게, 시간복잡도를 줄일 수 있게 수정해보려한다.
package Algorithm;
import java.util.ArrayList;
public class EuclideanAlgorithm {
public ArrayList<Integer[]> divideChocolateStick(int M, int N) { // 인원수에 따라 M,N을 골고루 나눠줄 수 있는 경우의 수 구하기
ArrayList<Integer[]> result = new ArrayList<>();
int GCD = euc(M,N); // 최대공약수
for(int i=1; i<=GCD; i++) { // i = 인원수
if(M%i==0&&N%i==0){
Integer[] ad = {i,M/i,N/i};
result.add(ad);
}
}
return result;
}
//////////////////////////////////수정된 부분//////////////////////////////////
public int euc(int M, int N) { // %사용하기 때문에 M,N 대소는 중요하지 않음. 어차피 큰게 왼쪽으로 알아서 바뀜
int rest = M % N;
// 나머지가 0이면 작은숫자가 최대공약수이므로 작은숫자 리턴
if (rest == 0) {
return N;
}
return euc(N, rest);
//////////////////////////////////수정된 부분//////////////////////////////////
}
}
M,N의 대소관계를 고려해줄 필요가 없다.
(M<N인 상황이라도 다음 재귀에서 순서가 바뀌기 때문)
package Algorithm;
import java.util.ArrayList;
public class EuclideanAlgorithm {
public ArrayList<Integer[]> divideChocolateStick(int M, int N) {
ArrayList<Integer[]> result = new ArrayList<>();
int GCD = gcd(M, N);
// 약수는 대칭적이라는 성질을 이용해 제곱근까지만 반복해도 구할 수 있다.
// (제곱근 보다 큰 약수는 제곱근보다 작은 약수에서 구할 수 있다.)
int sqrt = (int)Math.floor(Math.sqrt(GCD));
for(int left = 1; left <= sqrt; left++) {
if(GCD % left == 0) {
// 최대공약수의 약수인 경우 중 제곱근 보다 작은 약수의 경우
result.add(new Integer[]{left, M / left, N / left});
if(left * left < GCD) {
// 제곱근이 아닌 경우(제곱근 보다 작은)
int right = GCD / left; // 최대 공약수를 제곱근이 아닌 수로 나누면 제곱근 보다 큰 약수를 구할 수 있다.
result.add(new Integer[]{right, M / right, N / right});
}
}
}
Collections.sort(result, new Comparator<Integer[]>() { // 나눠줄 사람의 수를 기준으로 오름차순 정렬
@Override
public int compare(Integer[] o1, Integer[] o2) {
return o1[0].compareTo(o2[0]);
}
});
return result;
}
public int gcd(int m, int n) { // 최대 공약수(유클리드 호제법: Euclidean algorithm)
if (m % n == 0) return n;
return gcd(n, m % n);
}
}
9. 멱집합(꼭 다시풀기)
주어진 배열의 요소로 만들 수 있는 모든 조합을 list형으로 리턴하시오.
힌트: stack, 재귀를 활용해 보자.
package Algorithm;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;
public class PowerSet {
public ArrayList<String[]> missHouseMeal(String[] sideDishes) { // 멱집합
ArrayList<String[]> result = new ArrayList<>();
Arrays.sort(sideDishes); // 오름차순 정렬 (문제 조건)
Stack<String> stack = new Stack<>();
makeList(result, stack, sideDishes.clone(), 0);
result.sort((x,y) -> Arrays.toString(x).compareTo(Arrays.toString(y))); // 결과 오름차순 정렬
return result;
}
public ArrayList<String[]> makeList(ArrayList<String[]> result, Stack<String> stack, String[] side, int index){
if(index >= side.length){ // index>=side.length일 때. 즉, 마지막까지 검토를 했을 때
String[] arr = stack.toArray(new String[0]); // 추가해온 stack을 배열로 바꾸기
result.add(arr);
return result;
} else{
stack.push(side[index]);
makeList(result, stack,side, index+1);
stack.pop();
makeList(result, stack,side, index+1);
}
return result;
}
}
