(Java) 순열, 중복순열 만들기

최근에 어떤 시험에서 호되게 당해서ㅎㅎ 코드를 정리해둔다.

 

1) 1, 3, 5가 쓰여진 카드를 각각 rone, rthree, rfive장씩 갖고 있는 상황에서 
2) m장의 카드를 뽑아 옆으로 이어붙인다. ex) m==3일 때 3장을 뽑으면 135, 531, 553, 555, 113, 131, ... 이런 수들이 나온다.

3) 이 중 최댓값을 리턴한다.

 

 

import java.util.Scanner;

public class TexasHoldemMaxNumber {
    static int[] cards = {1, 3, 5}; // 카드 종류
    static int[] cardCount = {rone, rthree, rfive}; // 각 카드의 남은 장수
    static int maxValue = 0; // 최댓값 저장
    static int[] selected; // 선택한 카드 배열

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 사용자로부터 m 입력 받기
        System.out.print("Enter the number of cards to select (m): ");
        int m = scanner.nextInt();

        // 선택된 카드 저장 배열 초기화
        selected = new int[m];

        // 중복순열 계산 시작
        findMaxValue(m, 0);

        // 결과 출력
        System.out.println("Maximum number with " + m + " cards: " + maxValue);
    }

    // 중복순열을 이용해 m장의 카드 조합으로 최댓값 계산
    public static void findMaxValue(int m, int depth) {
        // 종료 조건: m장을 모두 선택한 경우
        if (depth == m) {
            // 선택된 카드 배열로 정수를 생성
            int number = createNumber(selected);
            // 최댓값 갱신
            maxValue = Math.max(maxValue, number);
            return;
        }

        // 중복순열로 카드 선택
        for (int i = 0; i < cards.length; i++) {
            if (cardCount[i] > 0) { // 남은 카드가 있을 때만 선택 가능
                cardCount[i]--; // 해당 카드를 사용
                selected[depth] = cards[i]; // 현재 깊이에 카드 선택
                findMaxValue(m, depth + 1); // 다음 깊이로 재귀 호출
                cardCount[i]++; // 백트래킹: 사용한 카드 반환
            }
        }
    }

    // 선택된 카드 배열로 정수를 생성하는 함수
    public static int createNumber(int[] selected) {
        int number = 0;
        for (int card : selected) {
            number = number * 10 + card; // 자릿수를 이동하며 숫자 생성
        }
        return number;
    }
}