BOJ 15663 - N과 M (9)

https://www.acmicpc.net/problem/15663

15663번: N과 M (9)

 

1. 아이디어

기존 중복을 허용하지 않고 순서있게 고르는 순열문제와 동일하지만 이번에는 N개의 수가 전부 다른 수가 아닐 수도 있기 때문에 좀 더 생각을 해봐야 한다.

 

만약 N개의 수가 1 4 4일 때, 중복을 허용하지 않고 2개를 순서있게 고르면 다음과 같다.

• 1 4
• 1 4
• 4 4

이렇게 되면 1 4가 중복되게 출력되는데 문제에서 중복 출력은 없도록 하라고 했으니 이걸 중복을 제거해주고 입력 순서를 유지해주는 자료구조 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, visit;
    static LinkedHashSet<String> map = new LinkedHashSet<>();
    static String numString = "";

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

        Arrays.sort(nums);

        rec_func(1, numString);

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

        bw.close();
    }

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

                if(visit[i] == 1) continue;

                selected[k] = n;
                visit[i] = 1;

                rec_func(k + 1, numString + n + " ");

                selected[k] = 0;
                visit[i] = 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];
        visit = new int[N+1];

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