BOJ 15665 - N과 M (11)

 

15665번: N과 M (11)

 

1. 아이디어

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

 

N개의 수 중 중복되는 수가 있을 수 있다는 사실을 알아야 한다. 

 

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

중복을 허용하여 순서있게 나열하면 다음과 같다

 

1 1

1 7

1 9

1 9

7 1

7 7

7 9

7 9

9 1

9 7

9 9

9 9

9 1

9 7

9 9

9 9

 

문제의 조건이 중복되는 수열은 출력하지 않는 것이므로 LinkedHashSet에 담아 출력해주면 된다.

2. 시간복잡도

중복 순열 문제이고 N과 M의 최댓값이 7이므로 7^7 = 823,543 <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, numString);

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

        bw.close();
    }

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

                selected[k] = n;
                rec_func(k + 1, 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());
        }
    }
}