[JAVA]BOJ 15654, N과 M (5)

N에서 중복이 되지않게 M개를 고른다. 그리고 예제를 보니 1 7 과 7 1 은 다른 수열로 친다.. 즉 순서 따진다는거고 이는 '순열'을 뜻한다. 순열 문제이다. 

순열은 순서를 고려하고 중복을 허용하지 않는 수열이다. 문제를 더 설명할건 없어서 바로 코드 설명으로 넘어가자.. 재귀를 사용했다.

 

1. 메인

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N, M, i;
    int[] arr, result;
    StringTokenizer st;

    st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
    arr = new int[N];
    result = new int[M];

    // 입력
    st = new StringTokenizer(br.readLine());
    for(i=0;i<N;i++)
        arr[i] = Integer.parseInt(st.nextToken());

    Arrays.sort(arr); // 정렬
    printSequence(arr, result, N, M, M);
}

 

각각 필드에 대해 입력을 받는다. 그리고 오름차순으로 출력해야 하므로 정렬을 해주었다. printSequence가 수열을 출력하는 함수이다. 매개변수 각각 (원래 배열, 결과배열, 숫자의개수, 뽑을숫자의 개수, 앞으로뽑을 숫자의개수)가 된다.

 

2. printSequence 함수

    public static void printSequence(int[] arr, int[] result, int N, int M, int toPick){
        int i, lastIdx;

        // base case -> 다 뽑았을때
        if (toPick == 0){
            for(i=0;i<M;i++)
                System.out.print(arr[result[i]] + " ");
            System.out.println();
            return;
        }

        // 결과배열의 idx, 초기에는 -1
        lastIdx = M - toPick - 1;

        // recursive case
        for(i=0;i<N;i++){
            if(checkRepetition(result, i, lastIdx) == 1){ // 중복 허용 X
                result[lastIdx + 1] = i;
                printSequence(arr, result, N, M, toPick - 1);
            }
        }
    }

먼저 변수 설명부터 하자면.. lastIdx는 result배열에 저장할때 결과를 저장하는 result배열의 인덱스값이다. toPick은 앞으로 뽑을 값.. 그러니까 7개중에 3개를 뽑는다면, 처음에는 앞으로 3개를 뽑아야 한다. 한 번 뽑고나면 앞으로 2개만 뽑으면 된다. 그걸 뜻하는 변수이다.

base case : N개중에 M개를 다 선택했을때는 출력하고 끝낸다. 선택할때 arr[ ] 의 인덱스를 선택해서 result배열에 저장하므로, 출력을 arr[result[ ]] <- 이런식으로 해야 원하는 값이 나온다.

recursive case : 반복문을 사용해서 실제로 뽑는다. result배열 안에 이번 차례의 값(i)가 없을때만 result배열에 값을 저장한다. 저장시에는 마지막으로 저장한 위치(lastIdx) 다음에 저장한다. 그리고 하나 뽑았으니 앞으로 뽑을 값(toPick)을 감소시킨다.

 

3. result 배열의 중복을 확인하는 함수

    public static int checkRepetition(int[] result, int N, int lastIdx){ // 중복을 확인하는 함수
        int i;

        for(i=0;i<=lastIdx;i++){
            if(result[i] == N)
                return 0;
        }
        return 1;
    }

지금까지 선택한 값들 중에서 이번에 넣을 값(N)이 있는지 없는지 확인하면 되므로 lastIdx까지만 확인한다.

---

아래는 전체 코드이다.

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

// 순열
public class BOJ15654 {
    public static int checkRepetition(int[] result, int N, int lastIdx){ // 중복을 확인하는 함수
        int i;

        for(i=0;i<=lastIdx;i++){
            if(result[i] == N)
                return 0;
        }
        return 1;
    }

    public static void printSequence(int[] arr, int[] result, int N, int M, int toPick){
        int i, lastIdx;

        // base case -> 다 뽑았을때
        if (toPick == 0){
            for(i=0;i<M;i++)
                System.out.print(arr[result[i]] + " ");
            System.out.println();
            return;
        }

        // 결과배열의 idx, 초기에는 -1
        lastIdx = M - toPick - 1;

        // recursive case
        for(i=0;i<N;i++){
            if(checkRepetition(result, i, lastIdx) == 1){ // 중복 허용 X
                result[lastIdx + 1] = i;
                printSequence(arr, result, N, M, toPick - 1);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, M, i;
        int[] arr, result;
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N];
        result = new int[M];

        // 입력
        st = new StringTokenizer(br.readLine());
        for(i=0;i<N;i++)
            arr[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(arr); // 정렬
        printSequence(arr, result, N, M, M);
    }
}