View

[Java] μˆœμ—΄(permutation)

μ±…μ½λŠ” 감자 2022. 8. 30. 21:33
λ°˜μ‘ν˜•
  • μˆœμ—΄κ³Ό μ‘°ν•©μ˜ 차이

    λ½‘νžŒ 자리 (μˆœμ„œμ˜ 의미 0 )β†’ μˆœμ—΄
    λ½‘νžŒ 자리 (μˆœμ„œμ˜ 의미 X )β†’ μ‘°ν•© 

πŸ’‘ μˆœμ—΄

nPr : μ—¬κΈ°μ„œ r은 루프λ₯Ό κ΅¬μ„±ν•˜λŠ” κ°œμˆ˜κ°€ λœλ‹€. κ·ΈλŸ¬λ‚˜, r의 μˆ˜κ°€ 미정이라면 μž¬κ·€λ‘œ κ΅¬ν˜„ν•΄μ•Ό ν•œλ‹€.

μž¬κ·€ κ²°μ • μš”μΈ: λ‹¬λΌμ§€λŠ” μˆ˜κ°€ 무엇인가? λ½‘νžŒ μˆ˜κ°€ μ €μž₯될 자리, λ½‘νžˆλŠ” μˆœμ„œ 등이 μ™€μ•Όν•œλ‹€!!

nPn

// 1,2,3을 ν¬ν•¨ν•˜λŠ” μˆœμ—΄μ„ μƒμ„±ν•˜λŠ” μž¬κ·€ν•¨μˆ˜ 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class PermutationTest1 {

    static int N;
    static int totalCnt;
    static int[] arr;
    static boolean[] isSelected;

    // nPn: 1λΆ€ν„° nκΉŒμ§€μ˜ 수 쀑 n 개λ₯Ό λͺ¨λ‘ λ½‘μ•„μ„œ μˆœμ„œμžˆκ²Œ λ‚˜μ—΄ν•¨
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        totalCnt = 0;

        arr = new int[N];
        isSelected = new boolean[N + 1]; // 0이 μ•„λ‹Œ 1λΆ€ν„° μ‹œμž‘

        permutation(0);
        System.out.println("총 경우의 수 :" + totalCnt);
    }

/*****  μž¬κ·€ ν•¨μˆ˜ κ΅¬ν˜„   *****/
    private static void permutation(int cnt) {

        if (cnt == N) {
            totalCnt++;
            System.out.println(Arrays.toString(arr));
            return;
        }

        // κ°€λŠ₯ν•œ λͺ¨λ“  μˆ˜μ— λŒ€ν•΄μ„œ 탐색
        for (int i = 1; i <= N; i++) {

            // μ‹œλ„λ˜λŠ” μˆ˜κ°€ μ„ νƒλ˜μ—ˆλŠ”κ°€?
            if (isSelected[i])// true -> μ‚¬μš©μ€‘μΈ 수
                continue;
            // μ‚¬μš©λ˜μ§€ μ•Šμ€ 수
            arr[cnt] = i;
            isSelected[i] = true;// κ·Έ μˆ˜κ°€ μ‚¬μš©μ€‘

            // λ‹€μŒ 수 λ½‘μœΌλŸ¬
            permutation(cnt + 1);
            // μ‚¬μš© λ˜μ—ˆλ˜ 수λ₯Ό λ‹€μ‹œ 되돌림
            isSelected[i] = false;
        }

    }
}

nPr

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class PermutationTest2 {

    static int N, R;
    static int totalCnt;
    static int[] arr, input;
    static boolean[] isSelected;

    // nPr: nκΉŒμ§€μ˜ 수 쀑 r개λ₯Ό λͺ¨λ‘ λ½‘μ•„μ„œ μˆœμ„œμžˆκ²Œ λ‚˜μ—΄ν•¨(1<=r<=n)

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        totalCnt = 0;
        input = new int[N];
        arr = new int[R];
        isSelected = new boolean[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            input[i] = Integer.parseInt(st.nextToken());

        }

        permutation(0);
        System.out.println("총 경우의 수 :" + totalCnt);
    }

    private static void permutation(int cnt) {

        if (cnt == R) {
            totalCnt++;
            System.out.println(Arrays.toString(arr));
            return;
        }

        // κ°€λŠ₯ν•œ λͺ¨λ“  μˆ˜μ— λŒ€ν•΄μ„œ 탐색 ->(input λ°°μ—΄μ˜ λͺ¨λ“  수λ₯Ό μ‹œλ„ν•΄μ•Όν•¨ )
        for (int i = 0; i < N; i++) {

            // μ‹œλ„λ˜λŠ” μˆ˜κ°€ μ„ νƒλ˜μ—ˆλŠ”κ°€?
            if (isSelected[i])// true -> μ‚¬μš©μ€‘μΈ 수
                continue;
            // μ‚¬μš©λ˜μ§€ μ•Šμ€ 수
            arr[cnt] = input[i];
            isSelected[i] = true;// κ·Έ μˆ˜κ°€ μ‚¬μš©μ€‘

            // λ‹€μŒ 수 λ½‘μœΌλŸ¬
            permutation(cnt + 1);
            // μ‚¬μš© λ˜μ—ˆλ˜ 수λ₯Ό λ‹€μ‹œ 되돌림
            isSelected[i] = false;
        }

    }
}

λ°˜μ‘ν˜•
Share Link
reply
λ°˜μ‘ν˜•
Β«   2024/11   Β»
일 μ›” ν™” 수 λͺ© 금 ν† 
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30