BOJ 15664 - N과 M (10)

15664번: N과 M (10)

 

 

1. 아이디어

N개의 자연수 중 M개를 중복없이 골라서 순서있게 나열하는 순열문제이다. 

여기에 비내림차순이어야 하므로 N개의 수를 정렬한 후 prev 인자를 통해 k번째 다음 자리인 k+1번 자리는 prev +1부터 탐색할 수 있도록 설정해준다.

 

 

여기서 N개의 숫자가 같은 것이 있을 경우를 생각해야 한다.

 

N개의 숫자가 9 7 9 1 이고 M이 2인 경우를 생각해보자

정렬을 하고 순열을 구해보면 다음과 같다.

 

1 7 

1 9

1 9

7 9

7 9

9 9

 

여기서 문제의 조건이 중복된 수열은 출력하지 않는 것이므로 중복은 제거하되 순서는 지켜주는 LinkedHashSet 자료구조로 감싸서 출력해주면 될 것 같다.

 

2. 시간복잡도

순열문제이므로 O(nPm)이다.

N과 M의 최댓값은 8이므로 8! < 1초라서 가능한 접근법이다.

 

3. 구현

import java.io.*;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, M;
    static int[] nums, selected;
    static LinkedHashSet<String> LHset = new LinkedHashSet<>();

    public static void main(String[] args) throws IOException {
        input();

        String numString = "";
        Arrays.sort(nums);

        rec_func(1, 0, numString);

        Iterator<String> iter = LHset.iterator();
        while (iter.hasNext()) {
            bw.write(iter.next()+"\n");
        }

        bw.close();
    }

    static void rec_func(int k, int prev, String numString) throws IOException {
        if (k == M + 1) {
            LHset.add(numString);
        } else {
            for (int i = prev + 1; i <= N; i++) {
                int n = nums[i];

                selected[k] = n;
                rec_func(k + 1, i, numString + n + " ");
                selected[k] = 0;
            }
        }
    }

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

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

        nums = new int[N + 1];
        selected = new int[M + 1];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
    }
}