[JAVA]BOJ 15656, N과 M (7)

오름차순이어야 한다는 조건이 없으니 이건 중복 순열 문제이다. 그냥 순열(백준 15654번)과 비슷한데, 중복체크하는 것만 빼면 된다.

 

1. 메인 --> 입력받고 오름차순 정렬함

2. printSequence 함수

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

    // base case -> 다 뽑았을때
    if (toPick == 0){
        for(i=0;i<M;i++)
            sb.append(arr[result[i]]).append(' ');
        sb.append('\n');
        return;
    }

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

    // recursive case 
    for(i=0;i<N;i++){
        result[lastIdx + 1] = i; // 중복 체크를 하지 않음
        printSequence(arr, result, N, M, toPick - 1, sb);
    }
}

lastIdx : 결과 배열(result)의 인덱스 번호

오름차순 정렬이 필요하지 않으니 smallest는 정의하지 않았다.(i는 0부터 시작..)

base case는 앞선 15654번, 15655번과 같다. 출력한다.. 근데 result배열에는 arr의 인덱스를 저장한것이므로 arr[result[ ]] 형식으로 출력해야한다. 아 그리고 그냥 출력했더니 시간초과나서 StringBulider로 출력했다.

recursive case는 중복체크를 하지 않으므로(1 1, 1 7 ... 가능) 전부 다 2개씩 선택한다.

---

아래는 전체 코드이다.

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

// 중복순열
public class BOJ15656 {
    public static void printSequence(int[] arr, int[] result, int N, int M, int toPick, StringBuilder sb){
        int i, lastIdx;

        // base case -> 다 뽑았을때
        if (toPick == 0){
            for(i=0;i<M;i++)
                sb.append(arr[result[i]]).append(' ');
            sb.append('\n');
            return;
        }

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

        // recursive case 
        for(i=0;i<N;i++){
            result[lastIdx + 1] = i; // 중복 체크를 하지 않음
            printSequence(arr, result, N, M, toPick - 1, sb);
        }
    }

    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;
        StringBuilder sb = new StringBuilder();

        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, sb);
        System.out.println(sb);
    }
}