BOJ 15666 - N과 M (12)

15666번: N과 M (12)

 

1. 아이디어

 

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

비내림차순이어야 하니까 재귀호출 시 prev를 넘겨주어 탐색하는 다음 자리는 이전 자리보다 큰 수, 즉 prev+1부터 탐색하도록 설정한다.

 

N개의 자연수 중 같은 수가 여러번 나올 수 있다는 것을 생각해야 한다. 

 

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

1 1

1 7

1 9

1 9

7 7

7 9

7 9

9 9

9 9

9 9

 

문제의 조건이 중복되는 수열은 출력하지 않는 것이므로 중복은 제거해주고 순서는 유지해주는 LinkedHashSet 자료구조를 이용해 출력해준다.

 

2. 시간복잡도

중복순열 문제이므로 N과 M의 최댓값이 8이니까 8^8 = 16777216 < 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, 1, 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; 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());
        }
    }
}