[백준] 15666번 문제 (N과 M (12)) 파이썬(Python) 및 자바(Java) 풀이

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

15666번: N과 M (12)

 

파이썬 풀이

n, m = map(int, input().split())
nums = sorted(list(map(int, input().split())))
temp = []

def dfs(start):
    if len(temp) == m:
        print(*temp)
        return
    remember_me = 0
    for i in range(start, n):
        if remember_me != nums[i]:
            temp.append(nums[i])
            remember_me = nums[i]
            dfs(i)
            temp.pop()

dfs(0)

 

자바 풀이

import java.io.*;
import java.util.*;

public class Main {

    static int n;
    static int m;
    static int[] nums;
    static boolean[] visited;
    static List<Integer> temp = new ArrayList<>();
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    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());

        nums = new int[n];
        visited = new boolean[n];

        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++){
            nums[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(nums);
        dfs(0);
        br.close();
        bw.close();
    }

    static void dfs(int start) throws IOException {
        if (temp.size() == m) {
            for(int j = 0; j < temp.size(); j++){
                bw.write(temp.get(j)+" ");
            }
            bw.newLine();
            bw.flush();
            return;
        }
        int remeberMe = 0;
        for(int i = start; i < n; i++){
            if (remeberMe != nums[i]){
                temp.add(nums[i]);
                remeberMe = nums[i];
                dfs(i);
                temp.remove(temp.size() - 1);
            }
        }
    }
}

대망의 n과 m 수열 문제 중 마지막 문제였다. 기념으로 자바로도 풀었다.

 

특별한 점은 remeber_me(rememberMe) 변수를 활용하여 중복 수열을 방지한 점이 있다.

그 외에는 전형적인 백트래킹 수열 풀이로 풀었다.