[백준 *Java] - N과 M (9) (15663)

N과 M(9)

15663번: N과 M (9)

👇 문제보기

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

---

 

👇 접근방식 (내생각 정리)

출력 쪽을 보게되면, 중복되는 수는 출력이되지 않습니다. 그래서 생각한 건, 재귀쪽에서 이전에 출력된 값들 중에, 동일한 값이 있는 경우를 제외해야하니?출력하는 값들을 저장해야할까 라는 생각을 먼저하게 됐습니다.

하지만, 저장을 하게되면 저장된 공간을 조회 해야해서 메모리랑 시간 복잡도가 올라갈 거라는 생각을 하여

이 방법을 우선적으로 하기보다는? 다른 방법을 고민했습니다.

또 다른 생각은 

Set을 통해 중복되지 않게 input Data를 한 번에 저장한 뒤에, 루프를 돌고

이후에 중복된 값을 가지고 루프를 도는 건 어떤가?

생각을 하였지만

이 방법도 사실 테스트케이스에 중복된 수가 하나만 나와있다보니 여러 개의 중복된 수일 경우에는 안될 거 같았습니다.

Map을 이용한다면?

가능은 하지만, 불필요한 정보로 key값이든? value 값이든 들어갈 거 같습니다.. 

그래도 일단 맵으로 구현한 뒤, 부족한 부분을 매우자 생각하고 코드를 구현했습니다.

구현 해서보니깐, 

HashMap으로 구현을했는데, 정렬이 안되어있어서, 정렬되는 HashMap이 있지 않을까 검색을 통해

LinkedHashMap을 찾아 사용해보았고,

정렬이되니깐 굳이 Map을 사용할 필요없지 않을까?

라는 생각이 이어져서, Set에서도 LinkedHashSet이 있지 않을까하여 찾아본 뒤 코드를 수정했습니다.

 

 

아래는 코드 구현입니다. 다른 N과 M문제와 다른게없어서 추가 설명은 생략했습니다...

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

public class Boj_15663 {


    static int N, M;
    static int[] inputDataArr;
    static boolean[] visited;
    static int[] arr;
    static LinkedHashSet<String> hs = new LinkedHashSet<>();

    public static void dfs(int depth) {
        // base case
        if (depth == M) {
            String temp = "";
            for (int i : arr) {
                temp += i + " ";
            }
            hs.add(temp);
            return;
        }
        // recur
        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                arr[depth] = inputDataArr[i];
                dfs(depth + 1);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) 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());

        visited = new boolean[N];
        inputDataArr = new int[N];
        arr = new int[M];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            inputDataArr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(inputDataArr);

        dfs(0);

        for (String value : hs) {
            System.out.println(value);
        }


    }

}