[Java]중복 순열(Permutation with repetition), 가위 바위 보 문제

중복 순열은 순열과 비슷하게 n개의 요소 중 r개를 순서에 상관있게 뽑는데,

 

중복을 허용하여 뽑는 경우의 수이다.

 

순서가 중요하되 중복을 허락한다는 말은 다음 그림을 보면 명확하다.

 

3^3 = 3 x 3 x 3 = 27

{A, B, C}세 개의 원소중 중복순열을 이용해 3개를 뽑는 경우의 수를 나타낸 그림이다.

 

자바로 구현하는 경우에도 중복을 허용한다는 부분만 반영을 해주면 된다.

 

이전 글에서 사용했던 코드의 경우, 중복을 피하기 위해 넣었던 isVisitied 배열을 제거하면 간단하다.

public class PermutationWithRepetition {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3}; // 순열을 만들 배열
        int n = arr.length; // 배열의 길이
        int[] output = new int[n]; // 순열을 저장하기 위한 배열

        per(arr, output, 0, n, 3); // 2개를 뽑는 경우(r=2)
        System.out.println("중복 순열의 개수: " + count);
    }

    static int count = 0;
    //순서를 지키면서 n 개중에서 r 개를 뽑는 경우
    static void per(int[] arr, int[] output, int depth, int n, int r) {

        if (depth == r) { // base condition
            count++;
            print(output, r); //순열 출력을 위한 print 함수
            return;
        }

        for(int i = 0; i < n; i++) {
                output[depth] = arr[i];
                per(arr, output, depth + 1, n, r); // 재귀함수 호출
            }
        }

    static void print(int[] arr, int r) { // 배열 출력을 위한 메서드
        for(int i = 0; i < r; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}

출력 결과는 아래와 같다.

// 출력 결과
1 1 1 
1 1 2 
1 1 3 
1 2 1 
1 2 2 
1 2 3 
1 3 1 
1 3 2 
1 3 3 
2 1 1 
2 1 2 
2 1 3 
2 2 1 
2 2 2 
2 2 3 
2 3 1 
2 3 2 
2 3 3 
3 1 1 
3 1 2 
3 1 3 
3 2 1 
3 2 2 
3 2 3 
3 3 1 
3 3 2 
3 3 3 
중복 순열의 개수: 27

 

연습문제 - 가위 바위 보 경우의 수

 

한 사람이 r번의 가위바위보를 하는 동안 낼 수 있는 모든 경우의 수를 구하는 문제이다.

 

메서드는 ArrayList<String[]> 타입을 리턴해야 하며,

 

String[]은 "rock", "paper", "scissor"중 한 가지 이상을 요소로 갖는 배열이다.

 

중요도는 "rock", "paper", "scissor" 순으로 높다.

 

import java.util.ArrayList;
import java.util.Arrays;

public class PermutationWithRepetition2 {
    public static void main(String[] args) {

        ArrayList<String[]> result = rockPaperScissors(3); // 최종 결과(r = 3)

        for (int i = 0; i < result.size(); i++) {
            System.out.println(Arrays.toString(result.get(i))); // 결과 출력
        }

    }
    public static ArrayList<String[]> rockPaperScissors(int r) {

        String[] arr = {"rock", "paper", "scissor"}; // 중복 순열을 만들 배열
        int n = arr.length; // 배열의 길이
        ArrayList<String[]> output = new ArrayList<>(); // 중복 순열을 저장할 ArrayList
        return per(arr, new String[]{}, output, 0, n, r);
    }

    static ArrayList<String[]> per(String[] arr, String[] playedSoFar, ArrayList<String[]> output, int depth, int n, int r) {

        if (depth == r) { // base condition
            output.add(playedSoFar);
            return output;
        }

        for (int i = 0; i < n; i++) {
            String[] concatArray = Arrays.copyOf(playedSoFar, playedSoFar.length + 1); // 새로 만든 String[] 배열. 요소 저장용.
            concatArray[concatArray.length - 1] = arr[i]; // 사이즈를 1 늘리고 늘어난 곳에 arr[i] 입력
            per(arr, concatArray, output, depth + 1, n, r); // 재귀함수 호출
        }
        return output;
    }
}

// 출력 결과
[rock, rock, rock]
[rock, rock, paper]
[rock, rock, scissor]
[rock, paper, rock]
[rock, paper, paper]
[rock, paper, scissor]
[rock, scissor, rock]
[rock, scissor, paper]
[rock, scissor, scissor]
[paper, rock, rock]
[paper, rock, paper]
[paper, rock, scissor]
[paper, paper, rock]
[paper, paper, paper]
[paper, paper, scissor]
[paper, scissor, rock]
[paper, scissor, paper]
[paper, scissor, scissor]
[scissor, rock, rock]
[scissor, rock, paper]
[scissor, rock, scissor]
[scissor, paper, rock]
[scissor, paper, paper]
[scissor, paper, scissor]
[scissor, scissor, rock]
[scissor, scissor, paper]
[scissor, scissor, scissor]

처음에 든 예시를 조금만 바꿔서 입력한 것을 알 수 있다.

 

ArrayList<string[]>타입을 리턴 시키기 위해 playedSoFar[] 배열을 만들어

 

경우의 수를 대입시킨 후  ArrayList<string[]>output 리스트에 add 해주었다.